New answers tagged

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