search
Log In
27 votes
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^*$

in Theory of Computation
edited by
3.5k views
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)*

6 Answers

35 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)^*$.

[Edit]

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

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

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

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.

Answer:

Related questions

19 votes
3 answers
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$
asked Apr 23, 2016 in Theory of Computation jothee 1.9k views
20 votes
2 answers
2
3.1k views
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
asked Sep 22, 2014 in Theory of Computation Kathleen 3.1k views
22 votes
2 answers
3
4.6k views
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\}$
asked Sep 22, 2014 in Theory of Computation Kathleen 4.6k views
19 votes
4 answers
4
2.9k views
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
asked Sep 22, 2014 in Theory of Computation Kathleen 2.9k views
...