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

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
What if the 3rd symbol from the right has to be 'a'?
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
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
66,699 users