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}.

The answers (contains spoilers)

  1. 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 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).*.
  2. 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 becomes ba.*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.
  3. 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 ::= abSa | aba (not ε, since n ≥ 1).
    c)   S ::= aSa | bSb | a | b | ε
Back