Chapter 13: Q17RE (page 900)
Describe how Turing machines are used to recognize sets.
Set A is recognized by a Turing machine T when the input x moves T from the start state \({s_0}\) to the last state for all \(x \in A\).
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
show that the grammar given in Example 5 generates the set \({\bf{\{ }}{{\bf{0}}^{\bf{n}}}{{\bf{1}}^{\bf{n}}}{\bf{|}}\,{\bf{n = 0,}}\,{\bf{1,}}\,{\bf{2,}}\,...{\bf{\} }}\).
Describe how productions for a grammar in extended Backus–Naur form can be translated into a set of productions for the grammar in Backus–Naur form.
This is the Backus–Naur form that describes the syntax of expressions in postfix (or reverse Polish) notation.
\(\begin{array}{c}\left\langle {{\bf{expression}}} \right\rangle {\bf{ :: = }}\left\langle {{\bf{term}}} \right\rangle {\bf{|}}\left\langle {{\bf{term}}} \right\rangle \left\langle {{\bf{term}}} \right\rangle \left\langle {{\bf{addOperator}}} \right\rangle \\{\bf{ }}\left\langle {{\bf{addOperator}}} \right\rangle {\bf{:: = + | - }}\\\left\langle {{\bf{term}}} \right\rangle {\bf{:: = }}\left\langle {{\bf{factor}}} \right\rangle {\bf{|}}\left\langle {{\bf{factor}}} \right\rangle \left\langle {{\bf{factor}}} \right\rangle \left\langle {{\bf{mulOperator}}} \right\rangle {\bf{ }}\\\left\langle {{\bf{mulOperator}}} \right\rangle {\bf{:: = *|/}}\\\left\langle {{\bf{factor}}} \right\rangle {\bf{:: = }}\left\langle {{\bf{identifier}}} \right\rangle {\bf{|}}\left\langle {{\bf{expression }}} \right\rangle \\\left\langle {{\bf{identifier}}} \right\rangle {\bf{:: = a }}\left| {{\bf{ b }}} \right|...{\bf{| z}}\end{array}\)
For each of these strings, determine whether it is generated by the grammar for infix expressions from Exercise 40. If it is, find the steps used to generate the string.
\(\begin{array}{*{20}{l}}{{\bf{a) x + y + z}}}\\{{\bf{b) a/b + c/d}}}\\{{\bf{c) m*}}\left( {{\bf{n + p}}} \right)}\\{{\bf{d) + m - n + p - q}}}\\{{\bf{e) }}\left( {{\bf{m + n}}} \right){\bf{*}}\left( {{\bf{p - q}}} \right)}\end{array}\)
Draw the state diagrams for the finite-state machines with these state tables.
In Exercises 16–22 find the language recognized by the given deterministic finite-state automaton
What do you think about this solution?
We value your feedback to improve our textbook solutions.
