The regular-expressions tag has no wiki summary.
2
votes
2answers
28 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
43 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
21 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
76 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
39 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
78 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 ...
0
votes
2answers
54 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
144 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
163 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
141 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
24 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
57 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
85 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
44 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
56 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
45 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
52 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.
0
votes
1answer
36 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
56 views
Is this DFA correct for the language $\{w \mid w \in \{ab\}^*\}$?
Language: $\{w \mid w \in \{ab\}^*\}$
1
vote
1answer
91 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
78 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
118 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
67 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
57 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
51 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, ...
2
votes
4answers
110 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
63 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
97 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
216 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
56 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
25 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
124 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
171 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
90 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
373 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.
