Chapter 13: Q37E (page 876)
Show that there is no finite-state automaton with two states that recognizes the set of all bit strings that have one or more 1 bits and end with a 0.
There is no finite-state automaton exist.
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 the string 11101 is in each of these sets.
a){0,1}* b){1}*{0}*{1}*
c){11} {0}*{01 d){11}*{01}*
e){111}*{0}*{1} f){11,0} {00,101}
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}\)
Let V = {S, A, B, a, b} and T = {a, b}. Determine whether G = (V, T, S, P) is a type 0 grammar but not a type 1 grammar, a type 1 grammar but not a type 2 grammar, or a type 2 grammar but not a type 3 grammar if P, the set of productions, is
\(\begin{array}{*{20}{l}}{{\bf{a) S }} \to {\bf{ aAB, A }} \to {\bf{ Bb, B }} \to {\bf{ \lambda }}{\bf{.}}}\\{{\bf{b) S }} \to {\bf{ aA, A }} \to {\bf{ a, A }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{c) S }} \to {\bf{ABa, AB }} \to {\bf{ a}}{\bf{.}}}\\{{\bf{d) S }} \to {\bf{ ABA, A }} \to {\bf{ aB, B }} \to {\bf{ ab}}{\bf{.}}}\\{{\bf{e) S }} \to {\bf{ bA, A }} \to {\bf{ B, B }} \to {\bf{ a}}{\bf{.}}}\\{{\bf{f ) S }} \to {\bf{ aA, aA }} \to {\bf{ B, B }} \to {\bf{ aA, A }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{g) S }} \to {\bf{ bA, A }} \to {\bf{ b, S }} \to {\bf{ \lambda }}{\bf{.}}}\\{{\bf{h) S }} \to {\bf{ AB, B }} \to {\bf{ aAb, aAb }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{i) S }} \to {\bf{ aA, A }} \to {\bf{ bB, B }} \to {\bf{ b, B }} \to {\bf{ \lambda }}{\bf{.}}}\\{{\bf{j) S }} \to {\bf{ A, A }} \to {\bf{ B, B }} \to {\bf{ \lambda }}{\bf{.}}}\end{array}\)
Construct a derivation of \({{\bf{0}}^{\bf{3}}}{{\bf{1}}^{\bf{3}}}\) using the grammar given in Example 5.
In Exercises 16–22 find the language recognized by the given deterministic finite-state automaton
What do you think about this solution?
We value your feedback to improve our textbook solutions.
