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 Samujjal Das commented Jan 25, 2017 reply Follow Share 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? 0 votes 0 votes Jason GATE commented Jan 25, 2017 reply Follow Share We can analyze with NFA first and then With DFA if required !!! 0 votes 0 votes Samujjal Das commented Jan 25, 2017 reply Follow Share Ok let's consider a NFA only. Can you give me some intuitive idea about how it can be done? 0 votes 0 votes Jason GATE commented Jan 25, 2017 i edited by Jason GATE Jan 25, 2017 reply Follow Share 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. 1 votes 1 votes Samujjal Das commented Jan 25, 2017 reply Follow Share @Jason Thanks but from your R.E, we can generate the string aaba, which is not acceptable. 0 votes 0 votes Jason GATE commented Jan 25, 2017 reply Follow Share See the Updated Answer !!!! 0 votes 0 votes Samujjal Das commented Jan 25, 2017 reply Follow Share Yes, clear now. Thanks man!! 0 votes 0 votes 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.