TOC_regular

Question

is this a regular Language?

L=(a+b)^*  | where No of (a)-no of(b) <=10

Comments

DCFL..

---

nicely explained @debashish make this an official answer.

I have one doubt why u have considered for $n_{a}(w) < n_{a}(w)$

we can simply prove $L = L_{0} \ \cup L_{2}\ \cup ...\ L_{K}$

as it is performing a linear comparision between $n(a)\ and\ n(b)$ hence it is a DCFL

---

corrected . It should be $n_{b}(w)$. thanks

Answer 1

Not regular.. It can be written as 

{L=(a+b)* | where No of (a)-10 <= no of(b)}

We need to count no of a's so we need stack.

But it is CFL.

Answer 2

It is non regualr language becoz to satisfy condition there are infinite values 

If a^nb^m/ n-m<=10 in this case dpda can be used but wt if we have counting comparison without order  as these cases are also present in above laguage 

So answer should be cfl .

Answer 3

No, it is not regular. Counting the number of $a$'s and $b$'s require to remember their encounters somehow. We need a stack for this. A deterministic PDA can do this. Hence the language is DCFL (accepted by DPDA).

Answer 4

Clearly,the given language is not regular b'coz there is comparison.Since we have to keep track of no. of a's to compare it with no. of b's ,here we need some memory element like stack.Thus language is clearly dcfl ,bcoz the pda that can accept the language is  deterministic.Since we have only 'a' and  'b'. in alphabet.