The tag has no wiki summary.

learn more… | top users | synonyms

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
92 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. ...
0
votes
0answers
25 views

regular expression length $\ge3$

my note says the length of the following reg expression is $\ge3$. $$((a\cup c)\cup b(a\cup c)\cup bc(b\cup c))(a\cup b\cup c)^*$$ I don't think it's $\ge3$ because: $$((a\cup c)\cup b(a\cup c)\cup ...
2
votes
1answer
33 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
141 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
50 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
30 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
23 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
235 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
258 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
81 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
64 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
91 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
65 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
131 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
115 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
83 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
837 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 ...
2
votes
1answer
740 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
423 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
74 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
306 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
90 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
143 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
162 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
78 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
68 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
78 views

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

Language: $\{w \mid w \in \{ab\}^*\}$
1
vote
1answer
168 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 ...
0
votes
2answers
138 views

Help with regular expression subset proof

Okay, so basically I'm just showing that two ways to express a regular expression are equal, and to do so, I'm showing they're subsets of each other. The expression is: $(A^*B^*)^* \subset ...
1
vote
2answers
412 views

For the regular expression, (a* + b*) . (a.b)* , does the following automaton recognise the language it describes?

I constructed the automaton below using the assumption that the language described by the regular expression above only accepted the following strings: Empty, aabab, babab, aaaabab, bbbabab etc ...
2
votes
2answers
75 views

For the language $\{w \mid w \in \Sigma^*, w \neq \lambda\}$, is the following regular expression correct?

For the language $\{w \mid w \in \Sigma^*, w \neq \lambda\}$, is the following regular expression correct? $(a+b)^+$ . Which is $(a+b)$ to the power of $+$ which I think accepts all combinations of ...
1
vote
1answer
103 views

Are these all the strings that the regular expression (a* + b*) . (a.b)* accepts or am I missing some?

From what I understand the regular expression (a* + b*) . (a.b)* accepts the following strings: Empty string, aaaaaaaaaababab, bbbbbbbbbbabab, aabab, babab, etc with different lengths of a, b and ab. ...
0
votes
2answers
75 views

What is the difference between the automatas for the regular expressions (a + b)* and (a* + b*)?

I know that the automaton for the regular expression (a + b)* will just have one state, where the initial state = the accepting state and there is one edge going into that state labelled a,b. Sorry, ...
4
votes
4answers
123 views

How does one show that these two expressions are the same?

I tried to compute the value of $\sin 75^\circ$ using the sine of standard values $(30^\circ, 45^\circ...)$ and did it by two ways. One, by expanding $\sin (45^\circ+30^\circ)$ and the other by ...
0
votes
1answer
77 views

Equivalent Expressions

Basically I'm trying to get this expression: $${(-1)^nn(n+1)\over2} + (-1)^{(n+1)}(n+1)^2$$ In this form: $$(-1)^{(n+1)}(n+1)(n+2)\over2$$ This is for a proof using mathematical induction, and I'm ...
1
vote
1answer
227 views

Negate regular expression

Suppose I have a simple regular expression describing a language like $(a+b)^* a?b (a+b)^*$ (a language in $\Sigma = \{a,b\}$ consisting of all words with substring $a?b$). I haven't found a general ...
1
vote
1answer
327 views

A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$

The following is an exercise in a book I am reading: Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words over $\Sigma$ that do not contain $ab$ as a sub-word. Find a regular ...
1
vote
1answer
75 views

Regular expression arithmetics

What are the rules of regular expression arithmetics ? For example: Let $\Sigma=\{0,1\}$ $1. 1+01=(\epsilon+0)1$. $2. (\epsilon+00)^*=(00)^*$
2
votes
1answer
33 views

Finding the mistake in a new way of generating FSMs from regular expressions

As described e.g. here (see pp. 2-3) a final state machine can be easily constructed from a regular expression. For the union of to expressions $e + f$ I need to look at the original way of ...
1
vote
1answer
206 views

Transformation of a regular expression

Let $a,b,c$ be regular expressions. Prove by transformation that $$(a^*b^*+c)^* \equiv (a+ (b+c)^*)^*$$ I tried to start with the second term $$(a + ((b+c)^*))^* = (a^*(b+c)^*)^* = ...
2
votes
1answer
216 views

Constructing finite state automata corresponding to regular expressions. Are my solutions correct?

I have drawn my answers in paint, are they correct? (4c) For the alphabet {0, 1} construct finite state automata corresponding to each of the following regular expressions: (i) 0 My Answer 4ci (ii) ...
0
votes
4answers
118 views

Proof for formal languages

Prove that for all languages $M,N \subseteq \Sigma^*$ applies: $(M+N)^* = (M^*N^*)^*$ Hi! I do'nt really understand why this applies: The first term uses the Kleene star on the union of M and ...
3
votes
1answer
487 views

Regular Expression Proof

I am trying to prove the following statement: If $S$ and $T$ are any regular expressions over a 1-letter alphabet and if $n$ is a natural, then the languages $(ST)^n$ and $S^nT^n$ are equal.