question 3 is a regular language I think?

RE=(a+b)*#(a+b)*

RE=(a+b)*#(a+b)*

0 votes

Give context-free grammars generating the following languages.

- The set of strings over the alphabet $\{a,b\}$ with more $a's$ than $b's$
- The complement of the language $\{a^{n}b^{n}\mid n\geq 0\}$
- $\{w\#x\mid w^{R}$ $\text{is a substring of $x$ for }$ $w,x \in\{0,1\}^{*}\}$
- $\{x_{1}\#x_{2}\#...\#x_{k}\mid k\geq 1,$ $\text{each}$ $ x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $ j,x_{i}=x_{j}^{R}\}$

0 votes

a. S->AaA

A->AA | aAB | bAa | a | ε

B->b

b. $\overline{L}$={$a^nb^m | n>m>1$} $\cup$ {$a^nb^m | m>n>1$} $\cup$ {(a+b)*b(a+b)*a(a+b)*}

Grammar for $\overline{L}$:

S->A | B | DbDaD

A->aaAb | aaCb

B->aBbb | aCbb

C->aCb | ε

D->aD | bD | a | b | ε

A->AA | aAB | bAa | a | ε

B->b

b. $\overline{L}$={$a^nb^m | n>m>1$} $\cup$ {$a^nb^m | m>n>1$} $\cup$ {(a+b)*b(a+b)*a(a+b)*}

Grammar for $\overline{L}$:

S->A | B | DbDaD

A->aaAb | aaCb

B->aBbb | aCbb

C->aCb | ε

D->aD | bD | a | b | ε