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

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 .