New answers tagged regular-expressions
0
Use the pumping lemma: If $L$ is regular, there is a constant $N \ge 1$ such that any string $\sigma \in L$ can be divided as $\sigma =\alpha \beta \gamma$ with $\lvert \alpha \beta \rvert \le N$, $\beta \ne \varepsilon$ so that for all $k$ the string $\alpha \beta^k \gamma \in L$.
Proof is by contradiction. Assume your $L$ is regular, let $N$ be the lemma's ...
1
This can also be proved easily using Myhill-Nerode theorem.
Myhill-Nerode Theorem: Given a language $ L \subseteq \Sigma^* $, Suppose $$ \forall x,y \in S, (x \neq y) \wedge (\exists z \in \Sigma^*
,L(xz) \neq L(yz)) $$ where S is an infinite set. Then L is not a
regular language.
(Here $L(w) = 1$ if $w \in L$ and $L(w) = 0$ if $w \notin L$.)
For the ...
0
Your language consists of all strings with an even number of $a$'s and an odd number of $b$'s. How do we construct a regular expression for such a language?
Let us assume for starters that the word starts with $bb$. Thus, it has the form
$$
bba^{n_1}ba^{n_2} \ldots ba^{n_m},
$$
where $m$ is even and $n_1+\cdots+n_m$ is even. This suggests grouping the $b$'s ...
1
Note that your grammar is regular. Quoting from wikipedia:
A grammar is regular when no rule has more than one nonterminal in its right-hand side, and each of these nonterminals is at the same end of the right-hand side.
Every regular grammar corresponds directly to a nondeterministic finite automaton, so we know that this is a regular language.
In theory, ...
0
It seems to me that you may simply consider the automata with states S, A, B, C and exit state X, and with the following transitions:
S -a-> A
S -b-> C
S -b-> X
A -a-> S
A -b-> B
B -a-> C
B -b-> A
B -a-> X
C -a-> B
C -b-> S
Right?
0
An epsilon transition (also epsilon move or lambda transition) allows an automaton to change its state spontaneously, i.e. without consuming an input symbol.
You need them for two cases
$1.$ The string or part of the string includes a Kleene star $^*$. E.g. $(10)^*$
$2.$ We have the option to choose between different strings. E.g. $0|1$
Now to make the ...
0
You almost got it Right in the comments, so I will give you the last push along with one way to think about it.
In the right automaton: the language of the automaton is simply $0\cdot L(q_1)$, where $L(q_1)$ is the set of words that can be accepted from $q_1$. Its not hard to see that a word $w$ is accepted from $q_1$ iff it $w$ is the empty word $\epsilon$,...
2
Here are the first few words accepted by the DFA on the right:
$$
0 \\
00 \\
000,010 \\
0000,0010,0100,0110 \\
00000,00010,00100,00110,01000,01010,01100,01110
$$
The DFA on the left accepts a subset of these words. Here are the words it does not accept:
$$
010 \\
0010,0100 \\
00010,00100,01000,01110
$$
Perhaps you can use these lists to obtain a guess on the ...
Top 50 recent answers are included
