Chapter 13: Modeling Computation

Show that there is no finite-state automaton with three states that recognizes the set of bit strings containing an even number of 1s and an even number of 0s.

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 given for postfix notation. If it is, find the steps used to generate the string.

\(\begin{array}{l}{\bf{a) abc* + }}\\{\bf{b) xy + + }}\\{\bf{c) xy - z*}}\\{\bf{d) wxyz - */ }}\\{\bf{e) ade - *}}\end{array}\)

Explain how you can change the deterministic finite-state automaton M so that the changed automaton recognizes the set I * − L(M).

Find all pairs of sets of strings A and B for which AB= {10, 111, 1010, 1000, 10111, 101000}.

Show that the hare runs the sleepy tortoise is not a valid sentence.

Determine whether 0101 belongs to each of these regular sets.

1. \({\bf{01*0*}}\)
2. \(0\left( {11} \right){\bf{*}}\left( {01} \right){\bf{*}}\)
3. \(0\left( {10} \right){\bf{*1*}}\)
4. \(0{\bf{*}}10\left( {0 \cup 1} \right)\)
5. \(\left( {{\bf{0}}1} \right){\bf{*}}\left( {11} \right){\bf{*}}\)
6. \({\bf{0*}}\left( {{\bf{10}} \cup {\bf{11}}} \right){\bf{*}}\)
7. \(0{\bf{*}}\left( {10} \right){\bf{*1}}1\)
8. \(01\left( {01 \cup 0} \right)1{\bf{*}}\)

What does the Turing machine described by the five-tuples \(\left( {{s_0},0,{s_0},0,R} \right),\left( {{s_0},1,{s_1},0,R} \right),\left( {{s_0},B,{s_2},B,R} \right),\left( {{s_1},0,{s_1},0,R} \right),\left( {{s_1},1,{s_0},1,R} \right)\), and \(\left( {{s_1},B,{s_2},B,R} \right)\) do when given

\(a)\)\(11\)as input\(?\)

\(b)\)an arbitrary bit string as input\(?\)

Find the output generated from the input string 01110 for the finite-state machine with the state table in

a) Exercise 1(a).

b) Exercise 1(b).

c) Exercise 1(c).

a) Define a type 1 grammar.

b) Give an example of a grammar that is not a type 1 grammar.

c) Define a type 2 grammar.

d) Give an example of a grammar that is not a type 2 grammar but is a type 1 grammar.

e) Define a type 3 grammar.

f) Give an example of a grammar that is not a type 3 grammar but is a type 2 grammar.