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.