# 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 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).*`

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

and`T::= aT | a`

c)`S ::= aSa | bSb | a | b | ε`