The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+21 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^*$

asked in Theory of Computation by Veteran (59.4k points)
retagged by | 1.5k views

3 Answers

+24 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. 
answered by Boss (19.7k points)
edited by
accepting (a+b)* printed wrong i guess
+3 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
answered by (167 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.
+3 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)*

answered by Active (2.2k points)

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

35,506 questions
42,827 answers
42,181 users