Peter Linz Edition 4 Exercise 5.1 Question 13.a (Page No. 134)

Question

L={$a^nb^n | n\geq 0$}
please show how $L^2$ is CFL

Comments

@Shaik Masthan'

bro , is this way of proof is good??I mean , is this formal method??

---

is this way of proof is good??

yes, it is one of the formal way,

Actually this is the correct method ( as i feel ), why because, we have to understood what are the strings we have then analyze how those are looking !

Answer 1

L = {a$^n$.b$^n$} = {ab,aabb,aaabbb,aaaabbbb,.....}

L$^2$ = L . L =$ \color{red}{\{\text{ab,aabb,aaabbb,aaaabbbb,.....}\}} . \color{Magenta}{ \{\text{ ab,aabb,aaabbb,aaaabbbb,.....}\}}$

= $\{\color{red}{\text{ab}}\color{magenta}{\text{ab}},\color{red}{\text{ab}}\color{magenta}{\text{aabb}},\color{red}{\text{ab}}\color{magenta}{\text{aaabbb}},\color{red}{\text{ab}}\color{magenta}{\text{aaaabbbb}},\color{red}{\text{ab}}\color{magenta}{\text{aaaaabbbbb}},......\color{red}{\text{aabb}}\color{magenta}{\text{ab}},\color{red}{\text{aabb}}\color{magenta}{\text{aabb}},\color{red}{\text{aabb}}\color{magenta}{\text{aaabbb}},\color{red}{\text{aabb}}\color{magenta}{\text{aaaabbbb}},\color{red}{\text{aabb}}\color{magenta}{\text{aaaaabbbbb}},......\}$

L$^2$ = ${\{\color{red}{\text{a}^p\text{b}^p}\color{magenta}{\text{a}^q\text{b}^q} | \;p >0 , \;q>0\}}$

Now, we must be already knowing that we can draw a PDA for it, 

How ?

first input p a's and pop using all b's , then if stack is empty or has Z$_0$, 

then  we can push q a's and then pop using all b's