TOC Question

Question

Sorry my BAD, it's an infinite language!

The given set {1, 101, 11011,1110111,......} is a Regular Language or CFL?

Comments

Oh, yes! you're right and n>0 or n>=0 ?

---

Why not n>=0 ?

---

n>=0 not possible because besides '0' we need at least one left 1 and one right 1 which is n>=1.......

trace the sequence you will get it 

{1,101, 11011,1110111,......} 

Answer 1

The language is L = {$1^{n}01^{n} \dotplus 1$, n>=1}

Notice here we need to check number of 1's before 0 is equal to number of 1's after zero. Which we can not achieve by DFA. So it is not regular.
This language is CFL as well as DCFL, At start we push all the 1's onto the stack, when we see 0 we ignore and after every 1 we pop 1's from the stack, if we end up with empty stack, we accept this language. So it is CFL as well as DCFL

Comments

n>=1..

---

Edited

Answer 2

By just looking at the kind of strings enumerated by the language, one can be under the impression that it is a CFL as it generates palindromes.

But the given language is finite and any finite language is always regular.

Comments

Kindly explain how!

---

We need to keep track of number of 1's before and after 0 as they need to be equal in this language.To do so, we need at least one stack. DFA cannot do it as it has finite memory and it's read head travels in only one direction which is from left to right i.e. once your head has advanced further in the tape after reading a symbol on the tape, it can never come back. So you can't keep track of previously scanned symbols on the tape. Hence, this language is not regular but can be simulated using one stack by a DPDA.

Hope it's clear now.

---

Indeed, thanks to you and everyone commented.

Means a lot