## Description

Question 1 (45 pts)

:

q2

q0 q4 q3

q1 q5

b

b

a

b

a

a

b

a

b b

a

a

Figure 1. M1

1. Using the state minimization algorithm you have learned, find and draw the minimal DFA that is

equivalent to M1. Show each step of your solution clearly.

2. Define each equivalence class of the automaton you have found at part-a with regular expressions.

Hint&Remark: In your regular expressions, you are allowed to use the symbol L to denote all

strings recognized by the automaton (e.g. [ϵ] = Lbaa).

3. Use MyHill-Nerode Theorem to prove that the language

L

′ = {a

n

b

mc

kd

u

: m + n = k + 2u and m, n, k, u ∈ N} is not regular.

## Question 2 (33 pts)

Give context-free grammars generating the following languages:

1. The strings over the alphabet {a, b} with more b

′

s than a

′

s.

2. A = {0

i1

j2

k

| i + k = j and i, j, k ≥ 0}

3. B = {w | the length of w is odd and w ∈ {0, 1}

∗} and draw parse tree for string 0011100.

## Question 3 (22 pts)

Give the (context-free) languages generated by each of the given grammars:

1. 1. G1 = (V1, Σ, R1, S1) where V1 = {S1, A} ∪ Σ, Σ = {0, 1} and

R1 = {S1 −> 0A0 | 1A1 | e

A −> 0A | 1A | e }

2. G2 = (V2, Σ, R2, S2) where V2 = {S2, B} ∪ Σ, Σ = {0, 1} and

R2 = {S2 −> B1B1B

B −> 0B | 1B | e }

2