# GATE2007-74

3.5k 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
3

We can reduce given automata to this- 0
Approach:

Sometimes there is a tricky question where even this  type of FA accept (a+b)* , but here b not accepted so that isn't possible.

We can have any number of b then a, q3 is unreachable so forget about it. For q1 and q2 we have transition for all symbol and it's within these two states so it will accepts everything after this. So b*a(a+b)*

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
1
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.

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

test for string a and epsilon we can easily get answer C

q0 is the initial state. q1 and q2 are the final states. String  is accepted.

Option a) doesn't generate string a.

option b) generates string b which is not accepted by the finite automata.

option d)  doesn't generates string a.

therefore option c is the answer.

## Related questions

1
1.9k views
Consider the following Finite State Automaton: The minimum state automaton equivalent to the above FSA has the following number of states: $1$ $2$ $3$ $4$
A minimum state deterministic finite automaton accepting the language $L=\{w\mid w \in \{0, 1\}^*,$ number of $0$s and $1$s in $w$ are divisible by $3$ and $5$, respectively $\}$ has $15$ states $11$ states $10$ states $9$ states
Which of the following languages is regular? $\left\{ww^R \mid w \in \{0, 1\}^+\right\}$ $\left\{ww^Rx \mid x,w \in \{0, 1\}^+\right\}$ $\left\{wxw^R \mid x, w \in \{0, 1\}^+\right\}$ $\left\{xww^R \mid x, w \in \{0, 1\}^+\right\}$
The language $L=\left\{0^i21^i \mid i \geq 0\right\}$ over the alphabet $\left\{0, 1, 2\right\}$ is: not recursive is recursive and is a deterministic CFL is a regular language is not a deterministic CFL but a CFL