Whether languages regular or not

Question

L1 ={ a^pb^q | p+q>=10^6}

L2= { a^mb^n | m-n>=10^6}

i m not getting this can someone help me with this

Answer 1

L1 ={ a^pb^q | p+q>=10^6}
 

• Then Complement of L1 will be :
• L1' ={ a^pb^q | p+q<10^6}
• And we can do that with Finite Amount of States.
• So L1' is Regular.Hence L1 is Also Regular.

(Applying Closure Property of Complementation)

L2={ a^mb^n | m-n>=10^6} 

• We can do this with the help of Single Stack, Hence it is CFL.

Comments

I am not getting how to construct the DFA for L1^'?

How can we know when a's will stop and b's will start?

---

We can analyze with NFA first and then With DFA if required !!!

---

Ok let's consider a NFA only. Can you give me some intuitive idea about how it can be done?

---

Sure Sir,

Let's take 

• L1' ={ a^pb^q | p+q<5}

For convenience, now We can write an Regular Expression like ,

R.E.

= ϵ + (a+b) + (ab) + (aab)  + (abb)  + (aaab) + (abbb).

For the Same we can design an NFA with finit amount of states (for string length 0-4) and an extra with Trap state.

Hope This will help clear your doubt.

---

@Jason

Thanks but from your R.E, we can generate the string aaba, which is not acceptable.

---

See the Updated Answer !!!!

---

Yes, clear now. Thanks man!!

---

Welcome Sir !!!!

---

@Jason GATE Sir, can you draw NFA for that?

---

How 2nd one is CFG....??

Answer 2

l1  is regular as we can make dfa for it
l2 is cfl because there is one comparison .