Chapter 13: Q39E (page 877)
Explain how you can change the deterministic finite-state automaton M so that the changed automaton recognizes the set I * − L(M).
By simply change each final state to a non-final state and change each non-final state to the final state.
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
Let V = {S, A, B, a, b} and T = {a, b}. Find the language generated by the grammar (V, T, S, P) when theset P of productions consists of
\(\begin{array}{*{20}{l}}{{\bf{a) S }} \to {\bf{ AB, A }} \to {\bf{ ab, B }} \to {\bf{ bb}}{\bf{.}}}\\{{\bf{b) S }} \to {\bf{ AB, S }} \to {\bf{ aA, A }} \to {\bf{ a, B }} \to {\bf{ ba}}{\bf{.}}}\\{{\bf{c) S }} \to {\bf{ AB, S }} \to {\bf{ AA, A }} \to {\bf{ aB, A }} \to {\bf{ ab, B }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{d) S }} \to {\bf{ AA, S }} \to {\bf{ B, A }} \to {\bf{ aaA, A }} \to {\bf{ aa, B }} \to {\bf{ bB, B }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{e) S }} \to {\bf{ AB, A }} \to {\bf{ aAb, B }} \to {\bf{ bBa, A }} \to {\bf{ \lambda , B }} \to {\bf{ \lambda }}{\bf{.}}}\end{array}\)
Determine whether all the strings in each of these sets are recognized by the deterministic finite-state automaton in Figure 1.
a){0}* b){0} {0}* c){1} {0}*
d){01}* e){0}*{1}* f){1} {0,1}*
Find a phrase-structure grammar that generates each of these languages.
\({\bf{a)}}\)the set of bit strings of the form \({{\bf{0}}^{{\bf{2n}}}}{{\bf{1}}^{{\bf{3n}}}}\), where \({\bf{n}}\) is a nonnegative integer
\({\bf{b)}}\)the set of bit strings with twice as many \({\bf{0's}}\) as \({\bf{1's}}\)
\({\bf{c)}}\)the set of bit strings of the form \({{\bf{w}}^{\bf{2}}}\), where \({\bf{w}}\) is a bit string
In Exercises 16–22 find the language recognized by the given deterministic finite-state automaton
Describe the elements of the set \({{\bf{A}}^{\bf{*}}}\)for these values of A.
a){10}b){111}c){0, 01}d){1,101}
What do you think about this solution?
We value your feedback to improve our textbook solutions.
