Chapter 13: Q18RE (page 900)
Describe how Turing machines are used to compute number-theoretic functions.
Turing machine T then computes some number-theoretic function when the input of \(n + 1\) ones result in the output with \(f\left( n \right) + 1\) ones.
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
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}\)
Suppose that S, I and O are finite sets such that \(\left| S \right| = n, \left| I \right| = k\), and \(\left| O \right| = m\).
\(a)\)How many different finite-state machines (Mealy machines) \(M = \left( {S,I,O,f,g,{s_0}} \right)\) can be constructed, where the starting state \({s_0}\) can be arbitrarily chosen?
\({\bf{b)}}\)How many different Moore machines \(M = \left( {S,I,O,f,g,{s_0}} \right)\) can be constructed, where the starting state \({s_0}\) can be arbitrarily chosen?
In Exercises 16–22 find the language recognized by the given deterministic finite-state automaton
Determine whether each of these strings is recognized by the deterministic finite-state automaton in Figure 1.
a)111 b) 0011 c) 1010111 d) 011011011
Let V = {S, A, B, a, b} and T = {a, b}. Determine whether G = (V, T, S, P) is a type 0 grammar but not a type 1 grammar, a type 1 grammar but not a type 2 grammar, or a type 2 grammar but not a type 3 grammar if P, the set of productions, is
\(\begin{array}{*{20}{l}}{{\bf{a) S }} \to {\bf{ aAB, A }} \to {\bf{ Bb, B }} \to {\bf{ \lambda }}{\bf{.}}}\\{{\bf{b) S }} \to {\bf{ aA, A }} \to {\bf{ a, A }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{c) S }} \to {\bf{ABa, AB }} \to {\bf{ a}}{\bf{.}}}\\{{\bf{d) S }} \to {\bf{ ABA, A }} \to {\bf{ aB, B }} \to {\bf{ ab}}{\bf{.}}}\\{{\bf{e) S }} \to {\bf{ bA, A }} \to {\bf{ B, B }} \to {\bf{ a}}{\bf{.}}}\\{{\bf{f ) S }} \to {\bf{ aA, aA }} \to {\bf{ B, B }} \to {\bf{ aA, A }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{g) S }} \to {\bf{ bA, A }} \to {\bf{ b, S }} \to {\bf{ \lambda }}{\bf{.}}}\\{{\bf{h) S }} \to {\bf{ AB, B }} \to {\bf{ aAb, aAb }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{i) S }} \to {\bf{ aA, A }} \to {\bf{ bB, B }} \to {\bf{ b, B }} \to {\bf{ \lambda }}{\bf{.}}}\\{{\bf{j) S }} \to {\bf{ A, A }} \to {\bf{ B, B }} \to {\bf{ \lambda }}{\bf{.}}}\end{array}\)
What do you think about this solution?
We value your feedback to improve our textbook solutions.
