Finite Automata Practice Questions

Correct Answer - Option B,C When we try to minimize the DFA given we can notice that states 3 and 4 have same inward and outward transitions and are indistinguishable, same for the states 2, 5. States 2 and 4 are distinguishable, because they have different transitions from state 1. In the final minimised DFA, we can clearly see that there are three states 1 , 2 , 4. For any given string with equal number of 1s and 0s, it will be accepted by the DFA.

$L_1=\{\epsilon +0(00)^\ast\}$ Now that is given language $L$, we have find order of it. $L^0=\{\epsilon\}$ $L^1 =L^0.L=\{\epsilon \}.\{\epsilon +0(00)^\ast\}=\{\epsilon+0(00)^\ast\}$ $L^2=L^1.L=\{\epsilon+0(00)^\ast\}.\{\epsilon+0(00)^\ast\}$ $=\{\epsilon+0(00)^\ast+0(00)^\ast0(00)^\ast\}$ $L^2=\{0^\ast\}$ $L^3=L^2.L=\{0^\ast\}.\{\epsilon+0(00)^\ast\}$ $=\{0^\ast+0^\ast0(00)^\ast\}$ $L^3=\{0^\ast \}$ Order of $L$ is $2$ such that $L^2=L^{2+1}$

Using any standard techniques to convert FSM into regex it's clear that, $L(D_1)=\{(001)^*+(000)^*+(010)^*+(101)^*\}^*$ $L(D_2)=\{(011)^*+(111)^*+(100)^*+(110)^*\}^*$ From this we could clearly eliminate first and second options. As for the remaining options, $L(D_1) \cap L (D_2)={\epsilon}$ as no other string apart from empty string could be \in common. If it does it must be reflected \in the regex which is apparently not true. Moreover, each of those languages construct strings from binary strings of length $3$. $D_1$ and $D_2$ use different binary strings of length $3$ for construction. For last option we could use the property of regex that if $A,B$ are any two regex then, $\left(A^{*}+B^{*}\right)^{*}=\left(A+B\right)^{*}$

We can combine the final state of $M_1$ with the start state of $M_2$ to recognize $L_1 L_2$. Remove the final state of $M_1$ as the new machine can accept $L_1$ also while it should accept only $L_1.L_2$.

Answer will be 2 states.

$L(M) = (a+b)^* \ a = \{a, aa, ba, aaa, aba, bba, \ldots\}$ $L(N) = (a+b)^* \ b = \{b, ab, bb, aab, abb, bbb, \ldots\}$ So, $L(M) \cap L(N) = \{\}$. So, in the minimal DFA, we just have $1$ start state with all transitions going to it self and no final state.

The regular expression is given as $\text{letter(letter+digit)*}$. This regular expression accepts the strings of one occurrence of a letter followed by any occurrence of letter and digits, such as \text{(letter,letter.letter,letter.digit,letter.digit.digit..∞)}. Option (A) This is wrong because it also accepts empty string that is $\epsilon$. Option (B): This is wrong because it accepts strings like $\text{(letter), (letter.letter) ...(letter.digit) ,(letter.digit.digit)}$, but it will not accepts the strings like $\text{(letter.digit.letter)}$. Option (C): It is the correct option. It will accept all the strings of $\text{letter(letter+digit)*}$. Option (D): It is wrong. Its RE is $\text{(letter(letter. digit)*)}$ and it will accept strings like ${(letter),(letter.letter.digit).(letter.letter.digit.letter.digit)...\infty }$. It will not accept strings like $(letter. letter),(letter. digit)$ etc.

The answer is $256$. We can reach the final state with all possible strings of length three on set $\{0,1\}.$ So there are $8$ ways to reach the final state and we will have a five-length string remaining where we have two options - either $0$ or $1,$ for each of the $5$ positions. So, total number of strings accepted will be $8 \times 2^5 = 2^8 = 256.$

Answer is option B. For any binary no, FSM read input from LSB and remain unchanged till first $1$, and it complement after that. Example: $\mathbf{100} \rightarrow \mathbf{100}$. $1010\mathbf{100} \rightarrow 0101\mathbf{100}$. Underline part is unchanged (till first $1$ from lsb) then $0$'s changed to $1$'s and $1$'s changed to $0$'s.

NO OPTIONS MATCHING. A is Wrong, since $abbb$ is accepted. ($1$ a is followed by more than $2$ $b$'s) C is Wrong, since $abba$ contains $abb$ as substring, but is still not accepted. D is Wrong, since $ab$ does not contain $aa$ as substring, but is still not accepted. B is wrong, since $\epsilon, b,bb,bbb,...$ are not accepting by given DFA.

$q_0, q_1$ and $q_2$ are reachable from $q_0$ on input $0011$. Correct Answer: $A$

Begin either with $0$ or $1$ Regular expression $:(0+1)(0+1)^*$. End with $0$ Regular expression $: (0+1)^*0$. End with $00$ Regular expression $:(0+1)^*00$. Containing the substring $00$ Regular expression $: (0+1)^*00(0+1)^*$. So, C is the correct answer.

We should solve these kinds of problems using process of elimination, $bb$ has even number of $b'$s but not accepted by the DFA, => option A is wrong $baba$ contains $bab$ but not accepted by the DFA, => option B is wrong $abab$ does contain the pattern $aba$, but it is accepted by the DFA => option D is wrong So, option C is correct

Answer should be option (A). Option (B) and (C) are clearly wrong. It says: $(\text{input } 11 \implies \text{output }01)$ and $(\text{input } 10 \implies \text{output }00)$, respectively, but, here for every single bit input the output is a $2$-bit sequence. Tracing out: suppose string is $0111$, we can see outputs represent the sum of previous input bit $+$ present input bit.

Correct Option: A. In (B) and (C) when the first letter of input is '$b$' we reach final state, while in the given DFA first letter '$b$' is not a final state. So, (B) and (C) are not accepting same language as the given DFA. In (D) we can reach final state when the last letter is '$a$', whatever be the previous transitions. But in the given DFA, when the first $2$ letters are '$b$' we can never reach the final state. So, (D) is also accepting a different language than the given DFA.

The language being accepted is $a^+$. So, complement of the language is $\{\epsilon\}$.

The correct automata for $L$ must accept every binary string ending with "011" and not accept any other binary string. Correct Ans: D

Option (C) and option (D) are cancelled out clearly because with $3$ $1$'s we can reach the final state. There is a string where we can reach the final state by $6$ $1$'s now $6$ is not odd but it is divisible by $3$. Hence, option (A) is correct.