The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
72 views

Prove/Disprove: $vwvw=vvww$ iff $\{v\}^*\{w\}^*=\{vw\}^*$

Let $\Sigma$ be an alphabet and $v,w\in \Sigma^*$. I'm trying to prove that: $$vwvw=vvww\quad\text{iff}\quad\{v\}^*\{w\}^*=\{vw\}^*.$$ I tried to do it by induction, with no success. Any help will ...
0
votes
1answer
39 views

Mathematical expression of largest $k$ numbers from $n$ numbers $(n>k)$

Can someone provide me a Mathematical expression of largest $k$ numbers from $n$ numbers $(n>k)$ eg $S$ is a 3x3 matrix with [6 8 5 ; 3 4 6 ; 9 0 5] where $n$ = 9 (elements) and I need to ...
1
vote
1answer
110 views

Translate a regular grammar to a regular expression

I want to translate the following grammar into a regular expression: Set of variables V := {S,T} Set of terminals Σ := {a,b} Set of relations S → "" S → aS S → bT T → ...
0
votes
1answer
212 views

Construction of Regular Expression

I have the problem of needing to construct a regular expression corresponding to the set of strings of 0's and 1's whose number of 0's is divisible by five and whose number of 1's is even. ...
2
votes
1answer
59 views

Regular expression for language

Let's have a language $L=\{\omega\in\{a,b,c\}^* | \omega $ contains $ab$ and does not contain $ba\}$ make a regular expression for this language. I've ended up with this one ...
0
votes
2answers
45 views

Concatenation of strings

We have two strings A and B. We have to find if for some n,m A concatenated n times equals B concatenated m times or not. I have made an interesting observation but am unable to prove it.It appears ...
1
vote
1answer
83 views

Question about Regular Expressions, DFA and relations

I have a few questions about discrete math, I can't fully grasp these concepts. For regular expression, what does the U symbol mean, at first I thought it meant that it was similar to or, for example ...
0
votes
2answers
91 views

Proving that a regular expression belongs to a certain language

I've often come by questions that require proving that a certain regular expression belongs to that language. Example: Given $\Sigma = \{0,1\}$, and the language $L$ of all the words that have ...
1
vote
2answers
162 views

Translate from logical formula to regular expression

I want to translate this formula in a regular expression: Explanation: The alphabet is : $\{a, b, c\}$ $w(p) = a$ , means on the position $p$ in the word stands an $a$. For the regular ...
1
vote
1answer
249 views

Proving that $L= \{a^nb^n, n\ge 0\}$ is not a regular language.

The questions i'm 'stuck' on is: Let $\Sigma = \{0,1,2\}$ be the alphabet, and let $L$ be the collection of all the languages that contains only words that have even length. Prove that there are ...
1
vote
1answer
31 views

Regular languages that are stutter-invariant but not star-free (LTL/FO-definable)

I am looking for simple examples and/or general ideas on regular languages (I am interested in finite words and infinite words alike) that are stutter-invariant (a language $L$ over an alphabet $A$ is ...
0
votes
0answers
58 views

Regular expression of: $\{ w \in \Sigma^* : w \text{ does not contain the substring 110} \}$.

Given $\Sigma = \{ 0,1,2 \}$, write a regular expression for $$\{ w \in \Sigma^* : w \text{ does not contain the substring 110} \}\;.$$ I know how to do a regular expression for a language that does ...
5
votes
1answer
733 views

Freshening up on discrete math (regular expressions)

I'm trying to freshen myself up on discrete math( I forgot a lot). I know this is a trivial question and not worth your time. But I forgot how to solve problems involving formal language theory. For ...
0
votes
1answer
354 views

What can be defined as a Regular Set

I'm currently studying compilers and am having some issues with understanding regular sets. For example, lets say I had a set of binary strings, (0, 1). Would all integers that are even and positive ...
1
vote
2answers
57 views

Is $\{w \in \Sigma ^* : |w|_2 mod 4 = 2\}$ a regular language?

Given alphabet $\Sigma = \{1,2,3\}$, is $\{w \in \Sigma^* : |w|_2 \bmod 4 = 2\}$ a regular language? I tried so hard on finding a regular expression but couldn't...
2
votes
1answer
144 views

L is language generated by the context free grammar G = (V, $\Sigma$, P, S)

L is language generated by the context free grammar G = (V, $\Sigma$, P, S), where $\Sigma$ = {a,b,c}, V = {S, A, B}, and the production set P is: S -> aSb | A A -> cAb | B B -> cb My question is, ...
0
votes
1answer
37 views

$L$ is a class of languages that cannot be represented by a regular expression. How to state cardinality of $L$.

$L$ is a class of languages that cannot be represented by a regular expression. The book says that the cardinality of $L$ is $2^{\aleph_0} > \aleph_0$ what's the logic behind getting the ...
0
votes
1answer
36 views

$L = L\bigl((b \cup ab \cup aab)^*(\lambda \cup a \cup aa)\bigr)$ . how does $bbbbbbabaabaa$ belong to L?

Let $L$ be the language generated by the regular expression $(b \cup ab \cup aab)^*(\lambda \cup a \cup aa)$. how does bbbbbbabaabaa belong to L? I know $(b \cup ab \cup aab)^*$ can be translated to ...
0
votes
1answer
96 views

L = (aa)*(bb)* checking if a string belongs to L* but not to L

L = (aa)*(bb)* checking if a string belongs to L* but not to L the string is: aabbaa I can't grasp the concept of putting a * (kleene star) on L, which already has a kleene star in it's definition. ...
2
votes
1answer
34 views

Regarding regular expression. why do the following strings not exist in the expression.

Let L be the language defined by the regular expression: (a U b U c)((ab U ac U b)*(a U b) U (aa)*) the answer book says that 'aaaa' and 'aaaaaa' do not belong to L. I can show that aaaa and aaaaaa ...
1
vote
1answer
42 views

set of all reg exp vs set of all languages

$\Sigma$ = {a,b,c,d,e} V = {A,B,C,D,E,F,G,H} According to the notes: The set of all regular expressions over $\Sigma$ is infinite and countable. The set of all languages over $\Sigma$ is infinite ...
0
votes
1answer
170 views

Right-linear grammar from regular expression

I made a right-linear grammar that from this regular expression: The alphabet is: $Σ = \{a, b, c\} $ Regular expression: $r = cc^*(ba)^*bb$ My solution, it seems a little too short like I'm ...
1
vote
1answer
51 views

NFA from regular expression

I'm trying to make an NFA from the following regular expression. I'm not sure about the edges between nodes $q2$ and $q4$, maybe someone can point out where everything went wrong.
0
votes
1answer
31 views

Converting regular expression to NFA.

I have the following two regular expressions and I need to convert them to NFA diagrams. I already did some and was wondering if they made any sense...i hope I'm not confusing the signs. ...
0
votes
1answer
24 views

Need help with the steps

Tried this problem several times and still cant get the right answer. Please help! https://webwork2.uncc.edu/webwork2_files/tmp/equations/ba/00ebd18c83856ce9c3b184a9a058a01.png
1
vote
1answer
251 views

Counting number of strings that contain substring matching Regular Expression

I have regular expression R, and I want to find F(n) is the number of strings of length n that strings that contain substring matching Regular Expression. Suppose the alphabet-size is M. We can apply ...
1
vote
2answers
282 views

Converting from NFA to a regular expression.

This is a NFA, I have been working to covert it to a regular expression. After I'am done, I arrive at an expression as follows $$ \left(((a\cup b)a^*b) (ba^*b)^*a\right)^* \left(((a\cup b)a^*b) ...
0
votes
1answer
83 views

Confusion about the generating function for a regular expression

Given a regex A = (a*b)*, I want to compute the Generating Function that enumerate this regex. The formula for the GF of that regex is ...
0
votes
2answers
67 views

Algorithm for a regular expression

This was a question for an exam that I received 0 points on, I'd like to get some input on what the correct answer should have been. Imagine that you are asked to write an algorithm P that takes a ...
1
vote
1answer
95 views

Give a regular grammar for L

Give a regular grammar for L= {a^n b^n : n<=100} I would do something like this : S---> A | empty string A---> aB| empty String B---> Ab but How do we keep count of the number in the grammar? ...
2
votes
2answers
66 views

Regular expressions, is it always true that (r+s)*=r*+s*?

I'm really confused about this, can some one please help me understand this better. If r and s are regular expressions then is it always true that (r+s)=r+s*? Are r and s sets and does the plus ...
1
vote
2answers
56 views

Strings: X^0 confusion

I've been given the set of string: X = {2,00}. I've been asked to perform various concatenation operations on it. ...
0
votes
1answer
29 views

simple differentation - help

how do you differentiate the expression vt with respect to x i.e. (d/dx)(vt) ? I know this is pretty simple but my mind has gone completely blank any help would be greatly appreciated! thank you :) ...
3
votes
2answers
138 views

Is this proof using the pumping lemma correct?

I have this proof and it goes like this: We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$. Then, the following proof is given: There is a $p$ ...
1
vote
2answers
50 views

Regular languages question

Describe these languages over $\Sigma={a,b}$ $\Sigma^{*}(a\cup\epsilon)b^*$ $a\Sigma\Sigma^*b\Sigma\cup b\Sigma\Sigma^{*}a\Sigma$ Just making sure I understand some basic concepts... First one ...
2
votes
2answers
117 views

Basic regular expressions problem

I'm in an intro to CS theory class learning about regular expressions. I was wondering if people could give me hints as to whether I'm on the right track for these problems. I hope this particular ...
1
vote
2answers
87 views

What are the states of this NFA?

I have to realize an NFA that recognizes the language of strings on the alphabet {a, b} ending with: bb, ba, baa. I thought that there must be the following states: $q_0$: the string ends with bb. ...
1
vote
2answers
957 views

Converting to regular expressions

I am really not sure about the following problem, I tried to answer it according to conversion rules the best I can. I was wondering if someone can give me some hints as to whether or not I am on the ...
3
votes
1answer
806 views

Is one regular language subset of another?

Let $L_1$ and $L_2$ be two regular languages given as regular expressions (in this type of tasks it often happens that $L_1 \subseteq L_2$, but vice versa it is false). Is there a nice way to ...
0
votes
0answers
433 views

regular expression and intersection

I have this language L that contains only one string: $a_{1}a_{1}a_{2}a_{1}a_{1}a_{2}a_{3}a_{1}a_{1}a_{2}a_{1}a_{1}a_{2}a_{3} ....a_{n}...a_{n}$ written more concisely ...
1
vote
0answers
44 views

Calculating the variance of the a regular expression assuming position dependent

Hello I am having trouble with a slightly biological problem I am given a regular expression $- [RK]-[LV]-[DE]-x(2)-Y$ this expression means that there is a string with the first position being an ...
1
vote
1answer
76 views

Proving or disproving regularity of a language

The question is as follows: If L1 and L2 are not regular and L1 ⊆ L ⊆ L2, then L is regular My intuition says that it's wrong so I've been looking for a ...
0
votes
1answer
329 views

Kleene Closure and determining whether a string x is in a set

If I'm given the following string $11101$, how do I know if it is in the following sets or not? $$\{11\}^*\{01\}^*$$ or $$\{111\}^*\{0\}^*\{01\}$$ from what I understand a Kleene Closure ($A^*$) ...
0
votes
1answer
92 views

Prove min(L) = all words in L that they don't have any prefix of themselves in L

We define the minimal words language of $L, \min(L)$, to be the language of all words in $L$ that don't have any prefix in $L$. Assume $L$ is regular language. I need to prove by building an ...
0
votes
1answer
145 views

Equivalence of regular expressions

I need to prove (or disprove, but I think those are proves), that the regular expression: r = (a+b)*b(a+b)*a(a+b)* (where + is OR and * is Kleene star) is ...
2
votes
1answer
196 views

Number of distinct strings in regular expression

Given the regular expression (1 + $\epsilon$ + 0 )(1 + $\epsilon$ + 0 )(1 + $\epsilon$ + 0 )(1 + $\epsilon$ + 0 ), how many distinct strings would this evaluation produce? How is the word "distinct" ...
0
votes
1answer
79 views

Is this NFA correct?

For the language L = $\{\Sigma^*. 0 .\Sigma^5 . 1. \Sigma^*\}$ The NFA must have 8 states. Also, what would be the upper bound on the number of states of a DFA recognizing L.
1
vote
1answer
75 views

Is this NFA correct for the language {w | w ends with an a and no a occurs between any occurrences of b}?

Language: {w | w ends with an a and no a occurs between any occurrences of b} The NFA must have exactly 3 states.
0
votes
3answers
80 views

Is this DFA correct for the language $\{w \mid w \in \{ab\}^*\}$?

Language: $\{w \mid w \in \{ab\}^*\}$
1
vote
1answer
173 views

regular expression/languages short questions

I'm stuck on these practice problems. If someone could help me solve them it would be great. What is a contextfree grammar for the langauge $L = \{a^i b^j c^j d^i \mid i,j \ge 0\}$ The following ...