Description
Problem 1. (25 points)
1. A palindrome is a string that reads the same backward as it does forward, i.e. a string w, where
w = w
R, where w
R is the reversal of the string w. Give a context-free grammar, expressed in BackusNaur form, that generates the set of all palindromes over the alphabet Σ = {a, b, c}.
2. Use bottom-up parsing determine whether the following strings belong to L(G), where G = (Σ, N, S, P),
where Σ = {a, b, c}, N = {S, A, B, C}, and P = {S → AB, A → aC, B → aB, B → bC, B → b, C →
cb, C → b}.
(a) abbb
(b) ababb
(c) acbaacb
(d) acbaaabcb
Problem 2. (25 points)
In extended Backus-Naur form (EBNF), the symbol ? indicates that the preceding symbol, or group of
symbols inside parentheses, is optional (can appear zero or once); the symbol ∗ indicates the the preceding
symbol or group can be repeated zero or more times; the symbol + indicates that the preceding symbol or
group can appear one or more times.
1. Describe the language generated by each of these grammars expressed in EBNF.
(a)
S ::= L+D?L+
L ::= a | b | c
D ::= 0 | 1
(b)
S ::= P D+ | D+
P ::= + | −
D ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
1
(c)
S ::= L*(D+)?L*
L ::= x | y
D ::= 0 | 1
2. Show that EBNF and BNF can generate the same languages by describing how productions for a
grammar in EBNF can be translated into a set of productions for the grammar in BNF.
Problem 3. (25 points)
Construct deterministic finite-state automata that recognize each of these languages.
1. the set consisting of the bitstrings 00, 11, and 010.
2. the set of bitstrings that start with 10 and end with one or more 1s.
3. the set of bitstrings consisting of an odd number of 0s followed by a final 1.
4. the set of bitstrings that have neither two consecutive 0s nor two consecutive 1s.
Problem 4. (25 points)
Consider this nondeterministic finite-state automaton:
start s0 s1
0
0,1
1
1. Construct a deterministic finite-state automaton that recognizes the same language.
2. What is the language that the automaton recognizes?
Aggie Honor Statement: On my honor as an Aggie, I have neither given nor received any unauthorized
aid on any portion of the academic work included in this assignment.
Checklist: Did you…
1. abide by the Aggie Honor Code?
2. solve all problems?
3. start a new page for each problem?
4. show your work clearly?
5. type your solution?
6. submit a PDF to eCampus?
2
