---

Syntax and Semantics

Lecture 3

---

Topics

In our previous lecture, we have seen how adding nondeterminism to the model of finite automata did not yield a more powerful model of computation. In particular, we saw that there is an algorithm that allows us to convert any nondeterministic automaton into an equivalent deterministic one.

In this lecture we shall see that regular expressions are also equivalent to finite automata, and that there are algorithmic conversions between these two formalisms. To this end, we shall first show how to convert a regular expression R into an NFA that recognizes the language denoted by R. Next, we shall show how, given a DFA M, we can build a regular expression describing the language L(M). As a tool in this conversion, we shall employ Generalized NFAs, which are just NFAs whose transitions may be labelled by arbitrary regular expressions. Both these conversions are achieved by means of algorithms, which you may find implemented in the DAT2 project developed last year by some of your colleagues.

Time and Location

Reading Material

• Primary Reading: Section 1.3 of Introduction to the Theory of Computation by Michael Sipser.

Exercises

• Complete any starred exercise you may have left over from the previous exercise class.

• Exercises 1.14(a)(*), 1.14(c), 1.15(a)(*), 1.15(c) and 1.16(a) on page 86 of Introduction to the Theory of Computation by Michael Sipser.

• (*) Is a finite language regular? Argue for your answer.

• (*) You are given a regular expression R. How would you find a regular expression that denotes the complement of L(R)? Argue for your answer.

• Let L be a language. Let rev(L) be the language consisting of all the reverses of the strings in L.
  • Define, for every regular expression R, a regular expression rev(R) denoting the language rev(L(R)). [Hint: Use induction on the structure of R.]
  • Use your solution to the above question to argue that regular languages are closed under the rev(.) operation. Can you establish this fact using a construction on automata?

• [Extra exercise] Let L be a language. Let pref(L) be the language consisting of all the prefixes of the strings in L.
  • Define, for every regular expression R, a regular expression pref(R) denoting the language pref(L(R)). [Hint: Use induction on the structure of R.]
  • Use your solution to the above question to argue that regular languages are closed under the pref(.) operation. Can you establish this fact using a construction on automata?

• [Programming Exercise] Write a program in your favourite programming language that, given a string and a regular expression, checks whether the string matches the regular expression.