Unit 2

REGULAR EXPRESSIONS

1. Let ∑ = {a,b}. Write regular expression to define language consisting of strings w.
2. Write some characteristics of regular expression.
3. Explain the methods to construct DFA.
4. Explain various strategies to build a finite automaton from a regular expression.
5. Construct ꞓ NFA for regular expression R,

R =(a+b)* abb

6.     Construct NFA for regular expression (1(00)* 1 + 01* 0)*.

7.     Construct DFA equivalent to regular expression

R=(ab+ba)* aa (ab+ba)*

8.     State and prove if L is a language accepted by DFA, then L is denoted by a regular expression.

9.     Consider FA shown in fig.

Find equivalent regular expression for the same.

10. State and explain Arden’s theorem.