Regular Expressions Practice Questions

The answer is C. You can see that both the states, $q_1$ and $q_2$ are final and are accepting $(a+b)^*$. States $q_1$ and $q_2$ are indistinguishable, so, they can be merged. $q_3$ is unreachable state, hence it can be removed.

The given DFA accepts all & only binary strings containing Odd number of $1's.$ So, option A is correct regular expression. Option B Counter-Example: Generates empty string. Option C Counter-Example: Doesn't generate $10011.$ Option D Counter-Example: Doesn't generate $1.$ WHY Option A: Go to the final state by reading $0^*1$, then stay in the final state by making either loop $0$ or loop $10^*1$ in any order, any number of times. So, $0^*1(0 + 10^*1)^*$ is the correct regular expression.

$S-4$ is confirmed. $R-3$ is true because everything it accepts ends with $1$; this is made mandatory only by $3$. This rules out option B and option D. Use string $01010$ and compare $P$ Vs $Q$; this makes $Q-2$ as confirmed. Hence, option C is correct.

The correct regular expression for the given DFA is $1(0+11)^*$.

Counter-example for option A: $011$ is not generated. Counter-example for option C: $000$ is not generated. Counter-example for option D: empty string is not generated. Correct expression is Option B.

Using Arden's theorem to find the regular expression : $A = \epsilon + A0 = \epsilon0^* = 0^*$ $B = A1 + B1 = 0^*1 +B1 = 0^*11^*$. As there are two final states, we should union both RE. $\implies 0^∗+0^∗11^∗=0^∗(\epsilon +11^∗)=0^∗(\epsilon+1^+)=0^∗1^∗$. $L$ contains all binary strings where any $1$ is not followed by any $0$.

Given DFA with $\sum = {0, 1}$ & p, q, r, s are the given states. State s is the initial state & State p is the final state. From, this DFA A, we can directly conclude few points: State r is the Dead State. DFA A is designed to accept all strings which starts with 1. The smallest string that will be accepted is 1. With conclusion 3, Option B is rejected. On reaching state p, we have 2 independent paths: Keep looping on state p, by reading 0 again and again. Reading 11 for coming back to final state p. Final RE: $1(0+11)^{*}$. Option C is Correct Answer.

We have two final states, $Q,R.$ First find the regular expression for set of all strings that end up at the initial state $P$ when running the given $\textsf{NFA}.$ Let's call this $P.$ Note that $P$ is the initial state, so, NFA execution starts at $P.$ Now, to end up on state $P$ at the end of the string, we can do any of the following: Read $'a'$, go to state $Q,$ then read any number of $b's$, then read $b$ to come back to state $P.$ So, $1 = ab^*b$. Read $'b'$, go to state $R,$ then read any number of $a's$, then read $a$ to come back to state $P.$ So, $2= ba^*a$. So, P = (1+2)^* = \[(ab^b)+(ba^a)]^$. Now, we want to find language of the given NFA$N$, whose final states are$Q,R.$So,$RegEx(N) = Q + R = P ab^ + Pba^* = P(ab^* + ba^) = $[(ab^b)+(ba^a)]^ (ab^ + ba^)$. Hence, Option D is Correct Answer.

Correct Option: B. (II) doesn't generate $11011$ which is accepted by the given DFA.