Homework 3
Instructions: Solve the exercises in this same document and include your answer below the
corresponding question. First, try to solve all problems individually, and then, meet with your team and
discuss the results. Once you are done, save it as a pdf file and upload it to the corresponding section in
canvas.
Student Id: A01638343 Name: Alejandro Moncada Espinosa
Student Id: A01644024 Name: Antoine Ganem Nuñez
Student Id: A01642781 Name: Aram Barsegyan
Exercises
1. (5 points) Is the following a regular grammar? Explain why it is or why it is not a regular
grammar.
𝑆→𝑧
𝑆 → zA
𝐴 → 𝑞 | 𝐴 |𝑡𝐵
𝐵 → 𝑐|𝑤𝐵|7
It isn’t a regular grammar because a non-terminal can’t generate itself, this can be seen in the
case of A and B.
2. (10 points) Design a context free grammar (CFG) for the language of words that are read the
same forwards and backwards from the alphabet {0,1}. Examples of valid strings:
ε,0,1,11,00,1001,11011. Examples of invalid strings: 011, 0101.
S→ε
S→0
S→1
S → 0S0
S → 1S1
3. (10 points) Given the grammar G:
𝑆 → 𝐴1𝐵
𝐴 → 0𝐴|ε
𝐵 → 0𝐵|1𝐵|ε
Determine if the following strings are derivable from G, that is, if they belong to the language L(G).
a) 00101
b) 1001
c) 0000
The strings a) and b) can be derivable from G but c) can´t because all valid strings must have at
least a 1.
4. (5 points) Describe with words what type of language does the following grammar generate.
𝑆 → 𝑞𝑆𝑟𝑆 | 𝑟𝑆𝑞𝑆 | 𝜀
This grammar generates a language consisting of strings where the letters 'q' and 'r' occur in
pairs, with an arbitrary number of pairs in between, and potentially with a single 'r' at the
beginning or a single 'q' at the end. In other words, it generates strings where 'q' and 'r' are
balanced, possibly with additional 'q's or 'r's on either side.
5. (10 points) Given the grammar:
𝑆 → 𝐴1𝐵
𝐴 → 0𝐴|ε
𝐵 → 0𝐵|1𝐵|ε
draw the derivation trees for the following two strings:
a) 00101
b) 1001
6. (10 points) Given the grammar 𝑆 → 𝑆𝑏𝑆|𝑆𝑐𝑆|𝑎 draw two different derivation trees for the string
abaca.
7. (10 points) Remove the useless variables from the following grammar.
𝑆 → 𝑎𝐴|𝐵|𝐷
𝐴 → 𝑎𝐴|𝑏𝐴|𝐵
𝐵 → 𝑏|𝜀
𝐶 → 𝑎𝑏𝑑
S -> aA|B
A -> aA|bA|B
B -> b|ε
8. (10 points) Remove unary and ε productions from the grammar:
𝑆 → 𝑎𝐴|𝐵
𝐴 → 𝑎𝐴|𝑏𝐴|𝐵
𝐵 → 𝑏|𝜀
9. (10 points) Given the grammar:
𝑆 → 𝐴𝑆𝐵|𝜀
𝐴 → 𝑎𝐴𝑆|𝑎
𝐵 → 𝑆𝑏𝑆|𝐴|𝑏𝑏
a) Remove the ε rules.
b) Remove the uniary rules.
c) Remove the useless variables.
d) Convert the grammar to ChNF.
10. (10 points) Given the language of well-balanced parenthesis:
a. Design a pushdown automaton for it.
b. Draw the trace table for the input string ((()))()
11. (10 points) Convert the following grammar into a pushdown automaton. Represent it using the
formal definition, not the diagram (you can include the diagram only as a reference).
𝑆 → 0𝑆1|𝐴
1. States (Q): {q0, q1, q2}
2. Input alphabet (Σ): {0, 1}
3. Stack alphabet (Γ): {Z0, 0, 1}
4. Transition function (δ):
δ(q0, 0, Z0) = {(q0, 0Z0)}
δ(q0, 1, Z0) = {(q2, ε)}
δ(q0, ε, Z0) = {(q1, ε)}
δ(q1, ε, 0) = {(q1, ε)}
δ(q1, 1, 0) = {(q1, ε)}
δ(q2, ε, 1) = {(q2, ε)}
δ(q2, 0, 1) = {(q2, ε)}
𝐴 → 1𝐴0|𝜀
5. Start state (q0): q0
6. Start symbol (Z0): Z0
7. Accept states (F): {q1}
