2 votes 2 votes Consider the following sets L1 = {apbq | p +q >= 106 } L2 = {ambn | m - n >= 106} Which of the following is a Regular Language? Also how to find the compliment of the given languages? Theory of Computation testbook-test-series test-series + – thehobo03 asked Dec 26, 2016 retagged Jun 4, 2017 by Arjun thehobo03 482 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply focus _GATE commented Dec 26, 2016 reply Follow Share L1 is regualr as we can make DFA for this language L2 is cfl as there is one comparison so its CFL 3 votes 3 votes saurabh rai commented Dec 26, 2016 reply Follow Share @kunal u r right.... we can make 2nd more simple by writing m >= n+106 3 votes 3 votes focus _GATE commented Dec 26, 2016 reply Follow Share yes. correct ! 0 votes 0 votes thehobo03 commented Dec 27, 2016 reply Follow Share But isn't there comparison in the first language as well? Both the languages look identical except the arithmetic operations. 0 votes 0 votes saurabh rai commented Dec 27, 2016 reply Follow Share @hobo understand 1 for p+q>=3. u ll get it if not then comment here i ll tell u.... 0 votes 0 votes thehobo03 commented Dec 27, 2016 reply Follow Share Didn't get it :/ 0 votes 0 votes saurabh rai commented Dec 27, 2016 reply Follow Share ^ok i m explaining u for for apbq | p+q >=3 assume p,q >=0 draw a nfa for abb with 4 states and attach a selfloop on final state for b draw a nfa for aab with 4 states and attach a selfloop on final state for b draw a nfa for aaa with 4 states and attach a selfloop on final state for b draw a nfa for aaab with 5 states and make a final state fo 3rd a and attach a selfloop on this final state for a and attach a selfloop on final state for b(this contains 2 final states) join all these nfa using e-transition. ----- u can try it on ur actual problem. 0 votes 0 votes thehobo03 commented Jan 3, 2017 reply Follow Share Hello, short for the late reply and thanks. In addition to these i would like to ask if drawing an nfa is the only solution to know whether a language is RL or not? 0 votes 0 votes Please log in or register to add a comment.