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
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.
In Exercises 16–22 find the language recognized by the given deterministic finite-state automaton
A context-free grammar is ambiguous if there is a word in \({\bf{L(G)}}\) with two derivations that produce different derivation trees, considered as ordered, rooted trees.
Show that the grammar \({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\) with \({\bf{V = }}\left\{ {{\bf{0, S}}} \right\}{\bf{,T = }}\left\{ {\bf{0}} \right\}\), starting state \({\bf{S}}\), and productions \({\bf{S}} \to {\bf{0S,S}} \to {\bf{S0}}\), and \({\bf{S}} \to 0\) is ambiguous by constructing two different derivation trees for \({{\bf{0}}^{\bf{3}}}\).
Construct a finite-state machine that models a newspaper vending machine that has a door that can be opened only after either three dimes (and any number of other coins) or a quarter and a nickel (and any number of other coins) have been inserted. Once the door can be opened, the customer opens it and takes a paper, closing the door. No change is ever returned no matter how much extra money has been inserted. The next customer starts with no credit.
a) Define a nondeterministic finite-state automaton.
b) Show that given a nondeterministic finite-state automaton, there is a deterministic finite-state automaton that recognizes the same language.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
