Tutorial I

We looked at Kari’s homework 3 questions 1 and 3 and homework 5 question 3. I also wanted to look at homework 5 questions 4 and 5, but we ran out of time. There’s always next lecture, though.

The questions

1. hw3(1) Find a regular expression that defines the language
a) L = {w ∈ {a, b}∗ | w contains at least one a and at least one b }
b) L = {w ∈ {a, b}∗ | w contains ab or ba (or both) as a subword }
c) L = {w ∈ {a, b}∗ | w contains both ab and ba as a subword }
2. hw3(3) For any language L, let its reverse Lᴿ = {wᴿ | w ∈ L} to be the set of the mirror images of its words. Prove that if L is a regular language then Lᴿ is also a regular language. (Hence the family of regular languages is closed under reversal.)
3. hw5(3) Construct context-free grammars that generate the following languages:
a) (ab|ba)∗ ,
b) {(ab)ⁿaⁿ | n ≥ 1},
c) {w ∈ {a, b}∗ | w is a palindrome },
d) {w ∈ {a, b}∗ | w contains exactly two b’s and any number of a’s },
e) {aⁿbᵐ | n ≤ m ≤ 2n}.

a) So $w$ either contains an $a$ followed by a $b$, or a $b$ followed by an $a$. So to me that makes .*(a.*b|b.*a).* (the surrounding .*s are to get a match with the whole string and not just the substring from the first a or b to the last b or a). Click here to see it on debuggex.
b) So $w$ contains either $ab$ or $ba$. I reckon it should be .*(ab|ba).*.
c) So $w$ contains either $ab$ followed by $ba$, or $ba$ followed by $ab$—or $w$ contains $aba$ or $bab$. So I reckon it should be .*(ab.*ba|ba.*ab|aba|bab).*.
Just reflect the regular expression (e.g. ab.*ba becomes ba.*ab).
You need to turn ^ (start of line) into \$ (end of line) and vice-versa, of course.
a)   S ::= abS | baS | ε
b)   S ::= abS | abT   and   T::= aT | a
c)   S ::= aSa | bSb | a | b | ε