i. Consisting of all strings of a's b's without any combination of double letters.

ii. over Σ = {a,b} containing at least one 'a' & at least one 'b'.

iii. Consisting of set of all strings that start with 'a' and do not have two consecutive 'b's.

r = 1•0•0• (0 + 1)

i. S → OSO | A | ∈

A → 1SO| ∈

ii. S → a Sc |A| ∈

A → aAb | ∈

S → a S a |b S b| ∈

G = {(A₁A₂A₃), (a, b), P, A₁}

Where P consists of the following productions :

A₁ → A₂A₃

A₂ → A₃A₁| b

A₃ → A₁A₂| a

L = {aⁿbⁿ / n > 0}

Simulate for ω = aaabb

L = { X, aXa. bXb, aaXaa, abXba......}

write simulation for

i. aa.a

ii. aaa.aaa

Write simulation for any two input strings.

PCP = {<p>|p is an instance of the Post Correspondence problem with a match}.

i. = { <B, ω> | B is an NFA that accepts input string ω}

ii. = {<R, ω> | R is a regular expression that generates string ω}