retagged by
13,394 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

4 states are enough for the language of all binary strings in which the third symbol from the right is a 1.

1

Related questions

21 votes
21 votes
5 answers
9
Arjun asked Nov 15, 2015
5,729 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
10
Akash Kanase asked Apr 18, 2016
3,463 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.