6 votes 6 votes 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 Theory of Computation theory-of-computation regular-language + – akshay_845 asked Jan 23, 2017 retagged Jun 4, 2017 by Arjun akshay_845 1.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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. Jason GATE answered Jan 23, 2017 selected Jan 23, 2017 by sudsho Jason GATE comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments Jason GATE commented Jan 25, 2017 reply Follow Share Welcome Sir !!!! 0 votes 0 votes iarnav commented Sep 19, 2017 reply Follow Share @Jason GATE Sir, can you draw NFA for that? 0 votes 0 votes Anmol Verma commented Oct 14, 2018 reply Follow Share How 2nd one is CFG....?? 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes l1 is regular as we can make dfa for it l2 is cfl because there is one comparison . focus _GATE answered Jan 23, 2017 focus _GATE comment Share Follow See all 0 reply Please log in or register to add a comment.