Problems
EECS2001E Problem Set Tutorial 3: May 24, 2019
1. Give a recursive definition of the set 𝑆 = {𝑎𝑛𝑏𝑐𝑛| 𝑛 ∈ 𝑁 ∪ {0}}
2. Give a recursive definition of all even length palindromes over Σ = { 𝑎, 𝑏}.
3. For each part below a recursive definition of a subset of {𝑎, 𝑏}∗ is given. Give a simple non-
recursive definition in each case. Assume that each definition includes an implicit last statement: “Nothing is in L unless it can be obtained by the previous statements.”
a) 𝑎∈𝐿; 𝑓𝑜𝑟𝑎𝑛𝑦𝑥 ∈𝐿,𝑥𝑎𝑎𝑛𝑑𝑥𝑏𝑎𝑟𝑒𝑖𝑛𝐿
b) 𝑎∈𝐿; 𝑓𝑜𝑟𝑎𝑛𝑦𝑥 ∈𝐿,𝑏𝑥𝑎𝑛𝑑𝑥𝑏𝑎𝑟𝑒𝑖𝑛𝐿
4. As discussed during the lecture, define L as
• aL;
• x L, ax L
• x, y L, bxy, xby and xyb are in L
• No other strings are in L
Prove that this is the language of strings with more a’s than b’s.
5. Do exercises 1.4, 1.5 (a, b, c, g, h), 1.6 and 1.7(a, b, c, d) of the textbook. We will discuss selected problems from this set during the tutorial.