retagged by
13,391 views
40 votes
40 votes
Let $L$ be the language of all binary strings in which the third symbol from the right is a $1$. Give a non-deterministic finite automaton that recognizes $L$. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?
retagged by

9 Answers

2 votes
2 votes

Let L be the language in which the third symbol from the right is a. Give a non-deterministic finite automaton that recognizes L.

 

Third input symbol is a while reading the input symbol from RHS

$(a's\ or\ b's)\ a\fbox{aa}$

$(a's\ or\ b's)\ a\fbox{ab}$

$(a's\ or\ b's)\ a\fbox{ba}$

$(a's\ or\ b's)\ a\fbox{bb}$


Firstly try to draw 4 states namely $aaa,aab,aba,abb$ from the initial state and name the intermediate states along with it.

Now in-order to find out what are the transitions for $aaa,aab,aba,abb$ you can do the following:

$aaa \overset{b}{\rightarrow} a\fbox{aab}$

$aaa \overset{a}{\rightarrow} a\fbox{aaa}$

$aba \overset{b}{\rightarrow} a\fbox{bab}$

$aba \overset{a}{\rightarrow} a\fbox{baa}$

.

.

$ \&\ likewise$

–1 votes
–1 votes
b.
third symbol from right is 1..

bit setting from right so no trap/dead state..
total 4 states required..
reshown by

Related questions

21 votes
21 votes
5 answers
1
Arjun asked Nov 15, 2015
5,725 views
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.
20 votes
20 votes
3 answers
2
Akash Kanase asked Apr 18, 2016
3,462 views
Consider the binary tree in the figure below:Give different steps for deleting the node with key $5$ so that the structure is preserved.