(a) Show that Turing machines, which have a read only input tape and constant…
PYQ GATE 1991
(a) Show that Turing machines, which have a read only input tape and constant size work tape, recognize preasely the class or regular languages.
(b) Let L be the language of all binary strings in which the third symbol from the right is a₁. Give a non-deterministic finite automaton that recognizes L. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?
Sign up free to check your answer
Sign up freeLoading lesson…

