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 22 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
Show that these equalities hold.
a) \({{\bf{\{ \lambda \} }}^{\bf{*}}}{\bf{ = \{ \lambda \} }}\)
b) \({\bf{(A*)* = A*}}\) for every set of strings A.
Suppose that A is a subset of\({{\bf{V}}^{\bf{*}}}\)where V is an alphabet.Prove or disprove each of these statements.
\(\begin{array}{l}{\bf{a)}}\,\,{\bf{A}} \subseteq {{\bf{A}}^{\bf{2}}}\\{\bf{b)}}\,\,{\bf{if}}\,{\bf{A = }}{{\bf{A}}^{\bf{2}}}{\bf{,then}}\,{\bf{\lambda }} \in {\bf{A}}\\{\bf{c)}}\,\,{\bf{A\{ \lambda \} = A}}\\{\bf{d)}}\,\,{{\bf{(}}{{\bf{A}}^{\bf{*}}}{\bf{)}}^{\bf{*}}}{\bf{ = }}{{\bf{A}}^{\bf{*}}}\\{\bf{e)}}\,\,{{\bf{A}}^{\bf{*}}}{\bf{A = }}{{\bf{A}}^{\bf{*}}}\\{\bf{f)}}\,\,\left| {{{\bf{A}}^{\bf{n}}}} \right|{\bf{ = }}{\left| {\bf{A}} \right|^{\bf{n}}}\end{array}\)
Find a phrase-structure grammar for each of these languages.
a) the set of all bit strings containing an even number of 0s and no 1s
b) the set of all bit strings made up of a 1 followed by an odd number of 0s
c) the set of all bit strings containing an even number of 0s and an even number of 1s
d) the set of all strings containing 10 or more 0s and no 1s
e) the set of all strings containing more 0s than 1s
f) the set of all strings containing an equal number of 0s and 1s
g) the set of all strings containing an unequal number of 0s and 1s
Determine whether the string 01001 is in each of these sets.
a){0,1}* b){0}*{10}{1}*
c){010}*{0}*{1} d){010,011} {00,01}
e){00} {0}*{01} f){01}*{01}*
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}\)
What do you think about this solution?
We value your feedback to improve our textbook solutions.
