search
Log In
19 votes
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
in Theory of Computation
edited by
1.3k views

1 Answer

27 votes
 
Best answer

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


edited by
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

18 votes
3 answers
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
asked Sep 16, 2014 in Theory of Computation Kathleen 2.7k views
20 votes
2 answers
2
3.4k views
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
asked Sep 16, 2014 in Theory of Computation Kathleen 3.4k views
19 votes
1 answer
3
1.3k views
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$?
asked Sep 16, 2014 in Theory of Computation Kathleen 1.3k views
33 votes
4 answers
4
4.5k views
Which combination of the following features will suffice to characterize an OS as a multi-programmed OS? More than one program may be loaded into main memory at the same time for execution If a program waits for certain events such as I/O, another program is immediately scheduled for execution If ... program is immediately scheduled for execution. (a) (a) and (b) (a) and (c) (a), (b) and (c)
asked Sep 16, 2014 in Operating System Kathleen 4.5k views
...