Chapter 13: Q20E (page 901)
What is the language recognized by the automaton in Exercise \(19\)\(?\)
The language recognized by the automaton is the empty set \(\emptyset \)
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
A palindrome is a string that reads the same backward as it does forward, that is, a string w, where \({\bf{w = }}{{\bf{w}}^{\bf{R}}}\), where \({{\bf{w}}^{\bf{R}}}\) is the reversal of the string w. Find a context-free grammar that generates the set of all palindromes over the alphabet {0, 1}.
Show that a set is generated by a regular grammar if and only if it is a regular set.
Give production rules in extended Backus–Naur form that generate all decimal numerals consisting of an optional sign, a nonnegative integer, and a decimal fraction that is either the empty string or a decimal point followed by an optional positive integer optionally preceded by some number of zeros.
Show that if \({\bf{M = (S,I,f,}}{{\bf{s}}_{\bf{o}}}{\bf{,F)}}\) is a deterministic finite state automaton and f (s, x)=sfor the state s∈Sand the input string x∈I*, then \({\bf{f(s,}}{{\bf{x}}^{\bf{n}}}{\bf{)}}\)=sfor every nonnegative integer n. (Here \({{\bf{x}}_{\bf{n}}}\) is the concatenation of ncopies of the string x, defined recursively in Exercise 37in Section 5.3.)
Give production rule in Backus-Naur form for an identifier if it can consist of
a. One or more lower case letters.
b. At least three but no more than six lowercase letter
c. One to six uppercase or lowercase letters beginning with an uppercase letter.
d. A lowercase letter, followed by a digit or an underscore, followed by three or four alphanumeric characters (lower or uppercase letters and digits.)
What do you think about this solution?
We value your feedback to improve our textbook solutions.
