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
Solution.
1. hpalindromei ::= hchari
hcharP chari
λ
hcharP chari ::= ahpalindromeia
bhpalindromib
hchari ::= a
b
2. (a) abbb
Using bottom up, C → b, A → aC abbb can be generated as Abb. In combination with the
productions, C → B, B → bC, abbb is generated ✷
(b) ababb
Using bottom up, C → b, B → bC, B → aB generates abb so ababb can be converted to abB.
Using C → b, A → aC ababb generates ab. Combining both, it is shown that ababb can be
generated by AB ✷
(c) acbaacb
Using bottom up, there is no way a string ending in acb can be generated in this language. Only
ending with c that ends as cb comes from C → cb. Going one step up, only possibilites end with
bcb from B → bC ∴ acbaacb is not in this language ✷
1
(d)
acbaaabcb Given (1)
acbaaabC fromC → cb (2)
acbaaaB from B → bC (3)
acbaaB from B → aB (4)
acbaB from B → aB (5)
acbB from B → aB (6)
aCB from C → cb (7)
AB from A → aC (8)
✷ (9)
2
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
(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.
Solution.
3
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.
Solution.
4
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?
Solution.
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?
5
Powered by TCPDF (www.tcpdf.org)
