The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
784 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 by Veteran (52.1k points)
edited by | 784 views

1 Answer

+25 votes
Best answer

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

by Veteran (56.4k points)
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,845 questions
54,764 answers
189,382 comments
80,279 users