1 votes 1 votes L1 = {apbq | p+q>=106} p,q, can only belong to set N. L1 Regular or not? Complement of L1 is definitely regular,so this should be regular,but it is confusing? Theory of Computation theory-of-computation regular-language + – resilientknight asked Aug 2, 2016 • retagged Jun 4, 2017 by Arjun resilientknight 752 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 5 votes 5 votes L is regular it is like that assume {apbq | p+q>=1 } then it is regular but {apbq | p- q>=1 } is non regular. since complement of regular is regular so complement of it is regular too. Prashant. answered Aug 3, 2016 • selected Aug 3, 2016 by Prashant. Prashant. comment Share Follow See all 14 Comments See all 14 14 Comments reply resilientknight commented Aug 3, 2016 reply Follow Share thank you sir 0 votes 0 votes vijaycs commented Aug 3, 2016 reply Follow Share no of states in its min- DFA ?? 0 votes 0 votes Prashant. commented Aug 3, 2016 reply Follow Share what i can say minimum 106 . 0 votes 0 votes dd commented Aug 3, 2016 reply Follow Share L = {anbm | (n+m)>=K, and K,n,m are natural numbers} then. regex for L $a^{*}(a^{1}b^{K-1}+a^{1}b^{K-1}+a^{2}b^{K-2}+.........+a^{K-1}b^{1})b^{*}$ is it ok? 2 votes 2 votes dd commented Aug 3, 2016 reply Follow Share The $\bar L$ is also regular and infinite. 0 votes 0 votes vijaycs commented Aug 3, 2016 i edited by vijaycs Aug 3, 2016 reply Follow Share correct @Debashish.... @Anirudh ... I think exact number of state should be = 2* 106 .. It needs little modification .. actually , we can merge state no. (106) and (106+1).. Please check it.. 3 votes 3 votes resilientknight commented Aug 3, 2016 reply Follow Share @everyone,i have a confusion,how is L' infinite? 0 votes 0 votes dd commented Aug 3, 2016 reply Follow Share @resilientknight, I guess you are thinking simply (p+q)<=k gives the complement because it becomes finite. Which is wrong because, complement of L is a set where the elements (or strings) are not a part of set L. For example: one of the possible subset of $\bar L$ = $b^{*}a^{*}$ (which is infinite) 0 votes 0 votes resilientknight commented Aug 3, 2016 reply Follow Share thank you @debashish for the insight. 0 votes 0 votes dd commented Aug 3, 2016 reply Follow Share @ vijaycs can we merge 106th and (106+1) th state ? 1 votes 1 votes vijaycs commented Aug 3, 2016 reply Follow Share yes , I agree .. thanks @Debashish Deka.. while drawing ..i was confused .. first i was doing the same but ... 0 votes 0 votes dd commented Aug 3, 2016 reply Follow Share So can we finalize min states as 2k for (p+q)>=k ? 0 votes 0 votes vijaycs commented Aug 3, 2016 reply Follow Share yes... and p,n should belong to any natural number ... 0 votes 0 votes resilientknight commented Aug 3, 2016 reply Follow Share awesome! 0 votes 0 votes Please log in or register to add a comment.