Problems
EECS2001E Problem Set Tutorial: June 21, 2019
1. Is the following language regular {𝑎𝑛𝑏𝑛+1| 𝑛 ≥ 0 } ?
2. Prove that 𝐿 = {𝑎𝑝| 𝑝 𝑖𝑠 𝑎 𝑝𝑟𝑖𝑚𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 } is not regular.
3. Prove that 𝐿 = {𝑎𝑛𝑏𝑛2| 𝑛 ≥ 0 } is not regular.
4. Show that 𝐿 = {𝑤 ∈ {0, 1} ∗ | 𝑤 h𝑎𝑠 𝑒𝑞𝑢𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 0′𝑠 𝑎𝑛𝑑 1′𝑠 } is not regular.
5. Exercise 2.3 (page 128 of Sipser, 2nd Edition).
6. Exercise 2.13(Page 129, Sipser, 2nd Edition).
7. Construct a CFG for {𝑎𝑖𝑏𝑗| 𝑖 = 𝑗 𝑜𝑟 𝑖 = 2𝑗 𝑜𝑟 𝑖 = 3𝑗, 𝑖, 𝑗 ≥ 0 }.
8. Construct a CFG for a set of strings over {𝑎, 𝑏} with two times as many a’s as b’s.
9. Construct a CFG for the language {𝑎𝑖𝑏𝑗| 2𝑖 = 3𝑗 + 1 }.