The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
101 views
find the DFA which accept strings such that 2nd symbol from RHS is $'a'$ .

$w=\{a,b\}^*$
asked in Theory of Computation by (71 points)
edited by | 101 views

1 Answer

+1 vote
Best answer

Either construct NFA and then convert it into DFA. Or  If you want to construct directly then here is the Idea :

While constructing DFA, Whenever you see $a$, think of it as 2nd last symbol. So, After this $a$ you can allow $a,b$ and accept. But after this when you see $a,b$ you must make a transition to relevant state.

The DFA will look like this :

answered by Boss (21.8k points)
selected by
0
What if the 3rd symbol from the right has to be 'a'?
+1
Then we will extend the idea and construct accordingly. We will have 8 states in minimal DFA with 4 final states.

Related questions

0 votes
1 answer
6
asked Nov 3, 2018 in Theory of Computation by Na462 Loyal (8.2k points) | 48 views


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

47,139 questions
51,387 answers
178,055 comments
66,699 users