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
- 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 } - 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.)
- 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}.
The answers (contains spoilers)
- Click here to reveal
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 firsta
orb
to the lastb
ora
). 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).*
.- Click here to reveal
This has a very simple answer, so if you didn’t get this one either get ready to kick yourself or re-hide the answer now and think some more.
Just reflect the regular expression (e.g.ab.*ba
becomesba.*ab
).
You need to turn^
(start of line) into$
(end of line) and vice-versa, of course.
Visibly, the reflection of a regex matches exactly the reflection of the language. One student asked about a formal proof of this (well done!): this can be done by induction on the length of the regex.- Click here to reveal
It helps to think of designing a little machine, with the nonterminals as states of that machine. I’ll do just the first three:
a)S ::= abS | baS | ε
b)S ::= abS | abT
andT::= aT | a
c)S ::= aSa | bSb | a | b | ε
- Click here to reveal