The Gateway to Computer Science Excellence
+25 votes

Consider the following Finite State Automaton:

The language accepted by this automaton is given by the regular expression

  1. $b^*ab^*ab^*ab^*$

  2. $(a + b)^*$

  3. $b^*a(a+b)^*$

  4. $b^*ab^*ab^*$

in Theory of Computation by Veteran (52.2k points)
edited by | 2.6k views

We can reduce given automata to this-


5 Answers

+29 votes
Best answer

The answer is C.

You can see that both the states, $q_1$ and $q_2$ are final and are accepting $(a+b)^*$.


  1. $q_3$ is unreachable state, hence it can be removed.
  2. States $q_1$ and $q_2$ are indistinguishable, so, they can be merged. 
by Boss (19.9k points)
edited by
accepting (a+b)* printed wrong i guess
+10 votes

given DFA accept a but option A and D cant so A and D are eliminated 
option B accept epsilon but given DFA cant accept epsilon so B eliminated 
Hence Ans is C

q3 i unreachabl state wo we remove it now both q1 and q2 are equivalent so they can combine now we easily find regular expression for it : b*a(a+b)*

by Active (2.7k points)
+5 votes
I will proceed with elimination of options
Option A: wrong because, string "ba" is accepted by given DFA. R.E given here can't generate it.
Option B: epsilon can't be accepted by given DFA. Given R.E generates epsilon
Option D: Same reason as option A. As "ba" can't be generated here too. The least it can generate are aa,baa,bbaa... so on..

Option C is correct. How???

After reaching q1, the DFA can accept any string generated by the alphabet{a,b}. b* is obvious from the given figure. to reach q1 we need atleast one a. Hence, b*a(a+b)^* is correct R.E
by (195 points)
minimal string accepts by A&D are 3a's, 2 a's but from the figure, we can see that string contain one 'a'  is minimal.
0 votes
test for string a and epsilon we can easily get answer C
by (65 points)
0 votes

State q3 is unreachable and state q1 and q2 are equivalent, so we can merge q1 and q2 as one state. The resulting DFA will be:

Clearly we can see that the regular expression for DFA is “ b*a (a+b)* ”.

by (331 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,523 answers
101,286 users