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.