CS 334 : Problem Set 3.
Problem 1. (10 points) Apply the DFA minimization algorithm to the DFA shown below. Show
the matrix of distinguishable pairs of states after each iteration of the loop. Finally, give a
regular expression that describes the language of the DFA.
Problem 2. (10 points) Consider the following languages:
𝑋 = {0
𝑘𝑤: 𝑘 ≥ 1, 𝑤 ∈ {0,1}
∗
, 𝑎𝑛𝑑 𝑤 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠 𝑎𝑡 𝑙𝑒𝑎𝑠𝑡 𝑘 0𝑠}
𝑌 = {0
𝑘𝑤: 𝑘 ≥ 1, 𝑤 ∈ {0,1}
∗
, 𝑎𝑛𝑑 𝑤 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠 𝑎𝑡 𝑚𝑜𝑠𝑡 𝑘 0𝑠}
For each language, prove whether it is regular or non-regular.
Problem 3. (10 points) Consider the following CFG G:
𝑋 → 𝑋𝑋 | 𝑌
𝑌 → 0𝑌1 | 01
a) What is the language generated by G?
b) Show that G is ambiguous.
c) Give an unambiguous grammar that generates the language of G.
d) Give an argument showing that your grammar in part (c) is unambiguous.
Problem 4. (10 points) Give a CFG for the language of palindromes over the alphabet {0,1}. Is
the language of palindromes that contain equal numbers of 0s and 1s context free? Either give
a CFG for this language or prove that it is not context free.
Problem 5. (10 points)
a) Prove that the language {𝑎
𝑥𝑏
𝑥𝑦𝑐
𝑦
: 𝑥, 𝑦 ≥ 0} is not context free.
b) Prove that the language {𝑎
𝑥𝑏
𝑥+𝑦
𝑐
𝑦
: 𝑥, 𝑦 ≥ 0} is context free.
Problem 6. (10 points) Give a CFG for {𝑎
𝑖𝑏
𝑖
𝑐
𝑘𝑑
𝑘
∶ 𝑖, 𝑘 ≥ 0} ∪ {𝑎
𝑖𝑏
𝑘
𝑐
𝑘𝑑
𝑖
∶ 1, 𝑘 ≥ 0}. Is your
grammar ambiguous?
