Access control powerpoint

Questions and Answers

Construct a deterministic finite automaton accepting language over the alphabet {a, b} in which every ‘a’ is followed by one or more ‘b’(s).

Examples

The desired language is:

L = {ε, ab, abab, abbbb, ababababab, ...}

The languages below are not accepted by this DFA

L1 = {ba, baab, bbaba, …}

L2 = {ε, a, aa, aaaa, b, bba, bbbbba, …}

Μ = (Σ, Ν, δ, q0, F)

Σ = {a, b}

Ν = {W, X, Y, Z}

q0 = W

F = {W, Y}

The state transition diagram of the language is

2. (3*5=15 points)

The regular expression 0*(10*)* denotes the same set as the regular expression:

True False (1*0)*1* T 0 + (0 + 10)* F (0 + 1)* 10(0 + 1)* F

Two regular expressions are equivalent if languages generated by them are same. Option (A) can generate all strings generated by 0*(10*)*. So they are equivalent. Option (B) can generate 0100 but 0*(10*)* cannot. So they are not equivalent. Option (C) will have 10 as substring but 0*(10*)* may or may not. So they are not equivalent.

3. (15 points)

Ν = {S, A, B, C}

Σ = {a, b, c, d}

Π =

{

S -> abS | abA | abB

A -> cd

B -> aB

C -> dc

}

S is S.

The simplified grammar G, G = (Ν, Σ, Π, S) is

Ν = {S, A}

Σ = {a, b, c, d}

Π =

{

S -> abS | abA

A -> cd

}

S is S.

4. (2*10=20 points)

Ν = {S}

Σ = {0, 1}

Π =

{

S -> 0S1S | 1S0S | ε

}

S is S

Is an ambigous grammar.

5. (25 points)

Given the grammar G, G = (Ν, Σ, Π, S), where

Ν = {S}

Σ = {0, 1}

Π = {S → ε, S → 0, S → 1, S → 0S0, S → 1S1}

S is S.

What is the language L, generated by the grammar G?

L = { w ε {0, 1}* | w = wR }