Epsilon Moves

**1.**

S –> aSa| bSb| a| b; the language generated by the above grammar is the set of ____________

**2.**

Which one of the following languages over the alphabet {0, 1} is described by the regular expression?

`(0+1)*0(0+1)*0(0+1)*`

**3.**

Which one is a FALSE statement?

**4.**

Match the following.

```
Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code optimization
```

**5.**

Let L = L1 ∩ L2, where L1 and L2 are languages as defined below.

```
L1 = {ambmcanbn | m, n >= 0 }
L2 = {aibjck | i, j, k >= 0 }
```

Then L is?

**6.**

Convert the NFA to DFA.

**7.**

Does epsilon ring any change in the automata.

**8.**

NFA-εs are defined because certain properties can be more easily proved on them as compared to NFA.

**9.**

E(q) is known ε-closure of q.

**10.**

ε-transitions does not add any extra capacity of recognizing formal.