The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
100 views
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) | 100 views

1 Answer

+4 votes

4 states is required.

answered by Boss (23.9k points)
0
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'.

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

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

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

0
Thanks For your time :)
0
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.


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

40,928 questions
47,581 answers
146,443 comments
62,311 users