Chapter 13: Q16RE (page 900)
Define a Turing machine.
An alphabet I has the space symbol B&a four-tuple made of a finite set \(S\) of states.
Over 22 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Let V = {S, A, B, a, b} and T = {a, b}. Find the language generated by the grammar (V, T, S, P) when theset P of productions consists of
\(\begin{array}{*{20}{l}}{{\bf{a) S }} \to {\bf{ AB, A }} \to {\bf{ ab, B }} \to {\bf{ bb}}{\bf{.}}}\\{{\bf{b) S }} \to {\bf{ AB, S }} \to {\bf{ aA, A }} \to {\bf{ a, B }} \to {\bf{ ba}}{\bf{.}}}\\{{\bf{c) S }} \to {\bf{ AB, S }} \to {\bf{ AA, A }} \to {\bf{ aB, A }} \to {\bf{ ab, B }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{d) S }} \to {\bf{ AA, S }} \to {\bf{ B, A }} \to {\bf{ aaA, A }} \to {\bf{ aa, B }} \to {\bf{ bB, B }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{e) S }} \to {\bf{ AB, A }} \to {\bf{ aAb, B }} \to {\bf{ bBa, A }} \to {\bf{ \lambda , B }} \to {\bf{ \lambda }}{\bf{.}}}\end{array}\)
Give the state tables for the finite-state machines with these state diagrams.
In Exercises 43–49 find the language recognized by the given nondeterministic finite-state automaton.
use top-down parsing to determine whether each of the following strings belongs to the language generated by the grammar in Example 12.
\(\begin{array}{*{20}{l}}{{\bf{a) baba}}}\\{{\bf{b) abab}}}\\{{\bf{c) cbaba}}}\\{{\bf{d) bbbcba}}}\end{array}\)
Show that the set \(\left\{ {{{\bf{1}}^{{{\bf{n}}^2}}}\left| {{\bf{n = 0,1,2,}}...} \right.} \right\}\) is not regular using the pumping lemma from Exercise 22.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
