Chapter 13: Q23SE (page 901)
Show that if \(A\) is a regular set, then so is \(\bar A\).
The give A is regular then \(\bar A\) is also regular
Over 30 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
Determine whether each of these strings is recognized by the deterministic finite-state automaton in Figure 1.
a)010b) 1101 c) 1111110d) 010101010
a) Construct a phrase-structure grammar that generates all signed decimal numbers, consisting of a sign, either + or −; a nonnegative integer; and a decimal fraction that is either the empty string or a decimal point followed by a positive integer, where initial zeros in an integer are allowed.
b) Give the Backus–Naur form of this grammar.
c) Construct a derivation tree for −31.4 in this grammar.
Find a phrase-structure grammar for each of these languages.
a) the set consisting of the bit strings 10, 01, and 101.
b) the set of bit strings that start with 00 and end with one or more 1s.
c) the set of bit strings consisting of an even number of 1s followed by a final 0.
d) the set of bit strings that have neither two consecutive 0s nor two consecutive 1s.
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}\)
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}\)
What do you think about this solution?
We value your feedback to improve our textbook solutions.
