edited by
2,057 views
11 votes
11 votes

Consider the following non-deterministic automaton,where $s_1$ is the start state and $s_4$ is the final (accepting) state. The alphabet is $\{a,b\}$. A transition with label $\epsilon$ can be taken without consuming any symbol from the input.

Which of the following regular expressions correspond to the language accepted by this automaton ?

  1. $(a+b)^*aba$
  2. $(a+b)^*ba^*$
  3. $(a+b)^*ba(aa)^*$
  4. $(a+b)^*$
  5. $(a+b)^*baa^*$
edited by

3 Answers

Best answer
10 votes
10 votes
On initial state S1, we have a loop labeled a,b which implies $(a+b)^*$

S1 on input b moves to S2. Then S2 on input a moves to S3 and S3 on $\epsilon$  reaches the final state S4.

Following these input transitions, we obtain $(a+b)^*ba$

But we have to account for the case when S4 on input a moves to S2.

Here we see, S4 on being given two successive a's forms a cycle/loop and comes back to the final state.

Hence, the regular expression corresponding to the language accepted by automaton would be $(a+b)^*ba(aa)^*$

PS: We do have an $\epsilon$ move from S3 to S1, but this is not important as S1 state captures $(a+b)^*$ meaning instead of moving to S3 and back to S1, there is an option to remain in S1 only. The given automata captures all binary strings ending with a "ba" followed by zero or more "aa".
selected by
0 votes
0 votes

we will eliminate a option if

1--The expression can't generate a string accepted by the machine(i.e expression can't generate required number of strings)

  OR

2--The expression generates a string not accepted by the machine(i.e expression generates more than the required number of strings)

we will check options:

A--can't generate "baaa" which is accepted by the machine. So eliminated.

B,C,E-- generates string "baaaa" which is not accepted by machine. So eliminated.

So option remaining is D.Hence it is the answer.

How i got the strings to check??

Here there is a epsilon transition from S3 to S4. So in a way it becomes final state(because,once you reach S3 you don't need any symbol to reach final state S4).

To reach S3 or S4 you need the string to end with odd number of a's(since if string ends with even number of a's, then by the end of string, the machine will be in S2).

So the grammar should generate string ending with odd number of a's

Answer:

Related questions

3 votes
3 votes
1 answer
1
4 votes
4 votes
2 answers
4
Arjun asked Dec 18, 2018
4,149 views
Which of the following decimal numbers can be exactly represented in binary notation with a finite number of bits ?$0.1$$0.2$$0.4$$0.5$All the above