retagged by
1,079 views

2 Answers

Best answer
8 votes
8 votes

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.
selected by
2 votes
2 votes
l1  is regular as we can make dfa for it
l2 is cfl because there is one comparison .

Related questions

0 votes
0 votes
2 answers
1
rohan.1737 asked Aug 17, 2018
670 views
Is there any way to check whether a language is regular or not without using Pumping lemma?