CFL or not ?

Question

I'm having problems with identifying CFL languages a lot recently.I understand L1 is not , but how come L2 is ? Understood 1 stack is enough but aren't there two comparisons ? Or that doesn't matter you can do any number of comparisons ? It's just number of stacks which are important ? In this case , 2 comparisons are needed n<k and k<2n. 

Any other fixed formula , to identify class of language which acts as easy guideline ? 

Comments

L1 is not cfl,more than one comparision

and L2 is cfl.L2={$a^{n}b^{2n}$ }. //for all 'b' s pop one 'a' and whenever b on initila stack symbol (z0) skip b's and accept the string.here only one comparision.

---

L1 can be constructed by concatenating the lang L={1^n0^n|n>1}. by closure properties L1 = L.L which is context free language. please correct my understanding

Answer 1

@vishal8492

this is one of the worst way to say whether a language is CFL or not only based on number of comparisons...if it was so then why pumping lemma for CFL was introduced?? there are many examples with a hell lot of comparisons but still CFL ,even regular sometimes....dont fall in such traps..

now coming back to question,
for L1....u can push all 1s onto the stack and then when 0s start coming pop them off...so for all 1s,all 0s will be popped off...now when again 1s start coming u dont have anything on the stack...for this we need a queue with some marking facilities so that we can move 2 ways and mark the inputs...this is LBA....thus the language mentioned is CSL not CFL..

for L2...
S-> aabbb / aaTbbb
T-> aTb / aTbb / epsilon..this is a CFG...
or L1 U L2..U Ln ..So , L1 = a^nb^(n+1), L2 = a^n b^(n+2), ....,Ln = a^n b^(2n-1)
NPDA is possible here

L1 is CSL and L2 is CFL(not DCFL)

Comments

alright.thanks!

---

think this way u just have to make sure that m!=n..means either a's should be greater than b's or b's should be greater than  a....just push all a's first..and for every b start popping a's...so if u r left with even a single a on top of stack and b gets over...then we r done...or for all b's all a's gets popped of and u see b again as input symbol then also we r done...so we are nt getting confused on any input symbol....its a DCFL..

---

It means 

Answer 2

L1 is not CFL, L2 is CFL

In L1 first you push all 1's, then for 0's pop every 1 to ensure #1's = #0's. So now when 1 come you cannot compare it with initial 0's and 1's as they are lost. So it's no CFL.

In L2 language can be written as {a^nb^n} U  {a^nb^n+1}.......{a^nb^2n}. As all these languages are CFL and we know CFL are closed under union. Therefore L2 is CFL. 

Comments

For L2 as I raised doubt , since n itself does not have any limit specified on it , won't it become infinte union in that case ? CFL isn't closed under infinite union. (I'll select answer , once my doubts are clarified so question isn't closed)

---

@vishal8492 'n'  and 'k' both are finite number. So union will never go infinite. If it would have to be infinite question will mention that.

---

Awesome , thanks

Answer 3

I am not sure about the answers. Please check.

1. L1 is not CFL. L1= {1ⁿ 0ⁿ 1^m 0^m, m=n and n>=1}. While parsing, 1ⁿ0ⁿ will be cancelled out. Similarly, 1^m0^m  will be cancelled out. Now, it can't be checked if m==n. Thus, not CFL.

2. This is CFL. L2= { aⁿ bⁿ U aⁿ bⁿ⁺¹  U ........ U aⁿ b²ⁿ }. Each of the grammars are CFL. Since CFL is closed on union, hence it is CFL.

Comments

Okay , although this looks good ; since n itself does not have any limit specified on it , won't it become infinte union in that case ? CFL isn't closed under infinite union.

---

How we will know how many union we have to take in consideration. If it is n+1 unions, then we can't again compare between a and b.

---

Looking at your logic, I am unsure whether it will be treated as finite union or infinite. Maybe someone else can help clear this doubt.

Answer 4

both are CFL

in L1 , on seeing 1 push the 1's onto stack and on seeing 0 again push the 0's now ...at top we have 0's...after that if if we see 1 again the pop 0 from the stack which is mached against the 1^n written at 3rd position...all 0 is over from stack..then if we see 0 then pop all the 1's from the stack..DPDA can be constructed

Comments

I think L1 is not CFL

what about the string 1110011000

it is not in the language but can be accepted by your method.