The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
85 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
59 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
55 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
28 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 :) ...
2
votes
2answers
122 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
49 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
111 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
81 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
721 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
657 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
407 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
43 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
72 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
279 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
137 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
148 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
54 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
76 views

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

Language: $\{w \mid w \in \{ab\}^*\}$
1
vote
1answer
162 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
131 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
344 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
100 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
71 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, ...
3
votes
4answers
121 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
220 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
318 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 ...
0
votes
1answer
72 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
188 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
213 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
108 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
479 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.