Problem $1$

Either prowe or disprove the following languages are regular or irregular.

$($a$)L=\{a^n{b}^m$:$nm\}$

$($b$)L=\{0^n{1}^m$:$n>m\}$

$($c$)L=\{c{c}^r$:cin$\{0,1{\}}^{**}\}$

Problem $2$

Design a pushdown automaton $($PDA$)$ that recognizes the following language:

$L(G)=\{a^k{b}^m{c}^n|k,m,n>0$ and $k=2m+n\}$

Problem $3$

Convert the given CFG below to PDA.

$Sa*A$

$Aa.S|bS|a$

Problem $4$

Convert the given PDA below to CFG$.$

$(q,1,Z)=(q,xZ)$

$(q,1,x)=(q,xx)$

$(q,0,x)=(q,x)$

$(q,,x)=(q,)$

$(q,0,Z)=(q,Z)$

Problem $5$

Claim if the following language can be recognized by a pushdown automata

$($PDA$).$ Prove$/$rationalize your claim.

$L(G)=\{a^i{b}^k{a}^i{b}^k|i,k>0\}$