4200 – Formal Languages: Homework #5
Due on Oct 17, 2019 at 2:00pm
Instructor: Dr.
1
Homework #5 4200 – Formal Languages (Instructor: Dr. ) Problem 1
Problem 1
30 points
Exercise 2.6. Give context-free grammars (CFGs) generating the following languages. 1. The set of strings over the alphabet Σ = {a, b} with more a’s than b’s
Answer:
S → Aa | MS | SMA
A → Aa | ε
M →ε|MM |bMA|aMb
2. The complement of the language {anbn | n ≥ 0} Answer:
A is the complement of the language {anbn | n ≥ 0}.
Thatis,Aisthelanguage: A={anbm |n̸=m} ∪{(a∪b)∗ba(a∪b)∗ }
Let’s call the leftmost language A1 and rightmost language A2 i.e. A = A1 ∪ A2. The CFG that generates A1 is
The CFG that generates L2 is:
S1 → aS1b | T | U T → aT | a
U → Ub | b
S2 → RbaR
R → RR | a | b | ε
Therefore, the CFG that generates language A when A = A1 ∪ A2 is:
S → S1 | S2
S1 → aS1b | T | U S2 → RbaR
T → aT | a
U → Ub | b
R → RR | a | b | ε
2
Homework #5 4200 – Formal Languages (Instructor: Dr. ) Problem 2
Problem 2
15 points
Exercise 2.9. Give context-free grammars (CFGs) generating the following language: A={aibjck |i=jorj=kwherei,j,k≥0}
Is your grammar ambiguous? Why or why not?
Answer
NotethatA=A1∪A2 whereA1 ={aibjck |i=j}andA2 ={aibjck |j=k}. The CFG that generates A1 is:
The CFG that generates A2 is:
S1 → aS2bS3 | ε S2 →aS2b|ε S3 →cS3 |ε
S4 → S5bS6c | ε S5 →aS5 |ε
S6 →bS6c|ε
The CFG that generates A would contain all the above 6 rules and starts with the following rule:
S → S1 | S4
The above CFG is ambiguous because you can derive two leftmost derivations each has a different parse tree.
Problem 3
15 points
Exercise 2.14. Convert the following CFG into an equivalent CFG in Chomsky normal form, using the procedure given in Theorem 2.9.
A →BAB | B | ε B →00 | ε
Answer: Below is the final result after following the procedure in the book. Note: For the Midterm 2, for this type of question, you will be asked to provide all intermediate steps, not just the final one.
S0 → BA1 | BS | SB | UU | BB | ε S → BA2 | BS | SB | UU | BB
B → UU
U→0 A1 → SB A2 → SB
3