The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
Ques:- How to create minimal DFA over w where w belongs to (a,b)* such 2nd symbol from RHS should be 'a'?
asked in Theory of Computation by (165 points) | 108 views

1 Answer

+4 votes

4 states is required.

answered by Boss (25k points)
Hi Abhishek,

Thanks for your solution but just I had one doubt Why in NFA diagram we are not having any transition for a,b means why it is 'phi'.

Regular expression to nfa conversion is easy . And we can easylly convert  nfa to dfa .

R.E------> nfa-------> dfa

The minimum number of states required in a minimal dfa for a string with nth symbol from RHS will be 2​​​​​​n.  

So in this case second symbol from RHS will give 4 states

Thanks For your time :)
In NFA  at state C we do not have any path for inputs a or b, hence "phi" is taken as empty or none value.

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

46,770 questions
51,221 answers
66,582 users