1.9k views

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^*$

edited | 1.9k views
0

We can reduce given automata to this-

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.
edited by
0
accepting (a+b)* printed wrong i guess

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)*

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
0
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.
test for string a and epsilon we can easily get answer C

1
2