-1
$\begingroup$

I don't know how to find the Language and the regular expression for each one. there are any special method for those kind of question? enter image description here

$\endgroup$
3
  • 3
    $\begingroup$ What have you tried? There is an algorithm that translates an NFA to a regular expression, but the automata here are quite simple. Try first to figure out the languages by trying different inputs, and then proceed by building expressions for them. Considering the components of the automata could be helpful. $\endgroup$ Commented Dec 30, 2020 at 17:21
  • $\begingroup$ right one 0(1+0)*0* and left one 0(10*10*)*0* $\endgroup$
    – user129239
    Commented Jan 2, 2021 at 12:10
  • $\begingroup$ I don't see why you keep vandalizing your own posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right for SE to distribute that content, and any vandalism will be reverted. You should already know that... $\endgroup$ Commented Jan 3, 2021 at 19:24

2 Answers 2

2
$\begingroup$

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 languages accepted by the DFAs. You can then try to see how the structure of the DFA corresponds to the language it accepts. For example, what do the states $D$ and $q_3$ signify? How do you reach them? How do you get to the accepting states $B$ and $q_1$?

$\endgroup$
4
  • $\begingroup$ thank u ,tell me what u think. the left one 0(10*10*)*0 the right one 0(1+0)*0 $\endgroup$
    – user129239
    Commented Jan 1, 2021 at 20:22
  • $\begingroup$ What about the word $000$? $\endgroup$ Commented Jan 1, 2021 at 23:42
  • $\begingroup$ so should i fix right one to 0(1+0)*0* and left one to 0(10*10*)*0* $\endgroup$
    – user129239
    Commented Jan 2, 2021 at 10:09
  • $\begingroup$ The right one now accepts $01$. Previously, it did not accept $0$. The left one still doesn't accept the word $00110$, but it does accept the word $011$. $\endgroup$ Commented Jan 2, 2021 at 13:02
0
$\begingroup$

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$, or $w$ ends with 0 (indeed, consider the component of the states $\{q_1, q_2\}$, reading 0 always leads to $q_1$, and reading $1$ always leads to $q_2$). Thus, $L(q_1) = \{ w: \text{ $w= \epsilon$ or $w$ ends with 0}\}$, and therefore the language of the automaton is given by the regex $0\cdot [\epsilon + (0+1)^* \cdot 0]$. The regex that you suggested is almost correct: it does not care about whether the word has to end with 0

  • In the left automaton: the language is simply $0\cdot L(B)$, where $L(B)$ is the set of words that can be accepted from $B$. Since $B$ is the only accepting state, a word is accepted from $B$ if its run from $B$ ends also in $B$. To get from $B$ to $B$, you have to read a word that contains only 0s, or to read a word of the form $( u\cdot u \cdot 0^*)^*$, where $u$ is a word that has exactly one letter that equals 1 and $u$ ends with 1. Indeed, you get to $C$ upon reading $u$ from $B$. Also you get to $A$ upon reading $u$ from $C$, and once you're in $A$, you have to read 0s to move back to $B$ and stay there. So $L(B)$ is given by the regex $r = 0^* + ( 0^*1\cdot 0^*1\cdot 0^*)^*$. Hence, the regex of the automaton is given by $0\cdot r = 0 \cdot [0^* + ( 0^*1\cdot 0^*1\cdot 0^*)^*]$. Note that maybe one can suggest a simpler regex (I leave that to you), yet this one goes well with the above explanation. Also, your regex assumes that when we move to $B$ for the first time, we have to see immediately 1. Finally, note that $L(B)$ is actually the set of words $w$ such that $\#_1(w)$ is a multiple of two, and 0 appears immediately after every 2nd 1.

$\endgroup$
4
  • $\begingroup$ thank you very much ! what about 0 in the right automata? $\endgroup$
    – user129239
    Commented Jan 2, 2021 at 14:39
  • $\begingroup$ can i get zero from 0(0+1)*0 in seems like the minimum is 00 maybe 0(0+1)*(0+epsilon) will be good? $\endgroup$
    – user129239
    Commented Jan 2, 2021 at 14:39
  • $\begingroup$ You're right, $L(q_1)$ contains also the empty word, edited the answer. $\endgroup$ Commented Jan 2, 2021 at 14:41
  • $\begingroup$ thank you very much $\endgroup$
    – user129239
    Commented Jan 2, 2021 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.