# GATE2002-21

1.3k views

We require a four state automaton to recognize the regular expression $(a\mid b)^*abb$

1. Give an NFA for this purpose
2. Give a DFA for this purpose

edited

NFA for regular expression $(a+b)^*abb$ and its equivalent DFA will be as follows:

edited
0

@Praveen Saini Sir What is the meaning of (a/b)* the question,is it (a+b)* what they have meant?

1
yes, afai think
0
praveen sir u r the best toc expert ever i seen
0

state   a          b

qo     q0q1    q0

q1        ^         q2

q2       ^           q3

q3       ^           ^

q0q1     q0q1     q0q2

q0q2      q0q1     q0q3

q0q3       q0q1     q0

q3 is final state so q0q3 also final state. Total 6 states.

Where am I going wrong? Pls help @Praveen Saini

1

@ , there is no need of q1, q2 and q3 check once.

0

@Praveen Saini sir construct an NFA for regular expression (a+b)* abb  and then convert it into DFA, will that be okk sir ??

0
Yes, this is good, but it is a time-consuming process, we can make DFA from the regular expression.
0
How you will make DFA directly?
0
it comes from practise

## Related questions

1
2.7k views
The smallest finite automaton which accepts the language $\{x \mid$ length of $x$ is divisible by $3\}$ has $2$ states $3$ states $4$ states $5$ states
The finite state machine described by the following state diagram with $A$ as starting state, where an arc label is and $x$ stands for $1$-bit input and $y$ stands for $2$-bit output outputs the sum of the present and the previous bits of the input outputs $01$ whenever the input sequence contains $11$ outputs $00$ whenever the input sequence contains $10$ none of the above
The aim of the following question is to prove that the language $\{M \mid M$ $\text {is the code of the Turing Machine which, irrespective of the input, halts and outputs a}$ $1\}$, is undecidable. This is to be done by reducing from the language $\{M', x \mid M'$ ... what is the second step $M$ must make? What key property relates the behaviour of $M$ on $w$ to the behaviour of $M'$ on $x$?