Chapter 13: Modeling Computation

Let \({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\) be the context-free grammar with \({\bf{V = }}\left\{ {\left( {\bf{,}} \right){\bf{S,A,B}}} \right\}{\bf{, T = }}\left\{ {\left( {\bf{,}} \right)} \right\}\) starting symbol \({\bf{S}}\), and productions \({\bf{S}} \to {\bf{A,A}} \to {\bf{AB,A}} \to {\bf{B,B}} \to {\bf{A,}}\)and \({\bf{B}} \to {\bf{(),S}} \to {\bf{\lambda }}\)

Construct the derivation trees of these strings.

\({\bf{a)}}\)\({\bf{(())}}\)

\({\bf{b)}}\)\({\bf{()(())}}\)

\({\bf{c)}}\)\({\bf{((()()))}}\)

Use Backus–Naur form to describe the syntax of expressions in infix notation, where the set of operators and identifiers is the same as in the BNF for postfix expressions given in the preamble to Exercise 39, but parentheses must surround expressions being used as factors.

Use Exercise 39 and finite-state automata constructed in Example 6 to find deterministic finite-state automata that recognize each of these sets.

a) The set of bit strings that do not begin with two 0s.

b) The set of bit strings that do not end with two 0s.

c) The set of bit strings that contain at most one 0 (that is, that do not contain at least two 0s).

Use the procedure you described in Exercise 39 and the finite-state automata you constructed in Exercise 25 to find a deterministic finite-state automaton that recognizes the set of all bit strings that do not contain the string 101.

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}\)

Use the procedure you described in Exercise 39 and the finite-state automaton you constructed in Exercise 29 to find a deterministic finite-state automaton that recognizes the set of all bit strings that do not contain three consecutive 1s.

Let G be a grammar and let R be the relation containing the ordered pair \(\left( {{{\bf{w}}_{\bf{0}}}{\bf{,}}\,{{\bf{w}}_{\bf{1}}}} \right)\) if and only if \({{\bf{w}}_{\bf{1}}}\) is directly derivable from \({{\bf{w}}_{\bf{0}}}\) in G. What is the reflexive transitive closure of R?

In Exercises 43–49 find the language recognized by the given nondeterministic finite-state automaton.

In Exercises 43–49 find the language recognized by the given nondeterministic finite-state automaton.