5 votes 5 votes Consider the following statements: $S_1:\{(a^n)^m|n\leq m\geq0\}$ $S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $ Which of the following is regular? $S_1$ only $S_2$ only Both Neither of the above Theory of Computation made-easy-test-series theory-of-computation regular-language + – Hirak asked May 25, 2019 edited May 27, 2019 by akash.dinkar12 Hirak 1.7k views answer comment Share Follow See all 18 Comments See all 18 18 Comments reply Verma Ashish commented May 26, 2019 reply Follow Share Both 0 votes 0 votes Hirak commented May 26, 2019 reply Follow Share explain. 0 votes 0 votes Verma Ashish commented May 26, 2019 i edited by Verma Ashish May 26, 2019 reply Follow Share Regular exp-- $S_1={a^*}$ ( take n=1 and m>=1, epsilon can be generated by taking n=0) $S_2=a^+ b^+$ 1 votes 1 votes Hirak commented May 26, 2019 reply Follow Share but how to check the condition whether n<=m or not for S1, doesn't it need pda? 0 votes 0 votes Verma Ashish commented May 26, 2019 reply Follow Share Consider a^6 Various (n,m) are (1,6),(2,3),(3,2),(6,1). So will a^6 be accepted or not? It will be accepted because there exist atleast one pair (n,m) such that n<=m. 1 votes 1 votes Verma Ashish commented May 26, 2019 reply Follow Share And we can give a pair (1,m) ==> a^m ,m>=1 It doesn't require any comparison and language accepted by (a^m+ eps) is same as S1. 0 votes 0 votes Hirak commented May 27, 2019 reply Follow Share @Verma Ashish Okay..thank u.. :) one more thing, say in case of S2 if we were given intersection instead of union then it wouldn't have been regular right? 0 votes 0 votes Verma Ashish commented May 27, 2019 reply Follow Share Yes then it will be CFL 1 votes 1 votes Hirak commented May 27, 2019 reply Follow Share okay.. :) 0 votes 0 votes akash.dinkar12 commented May 27, 2019 reply Follow Share @Hirak Try to type the question instead of posting screenshot in the above manner 0 votes 0 votes Hirak commented May 27, 2019 reply Follow Share It is clearly visible thats why done so.. 0 votes 0 votes srestha commented May 27, 2019 reply Follow Share and if the first question is $\left \{ \left ( a^{n} \right )^{m}.b^{n} \right \}$, then it would be NCFL or CSL?? 1 votes 1 votes Verma Ashish commented May 27, 2019 reply Follow Share @srestha $L=\{\epsilon, a^+b,(aa)^+bb,(aaa)^+bbb,\ldots\}$ i don't know how it will be NCFL or CSL.. 0 votes 0 votes srestha commented May 27, 2019 reply Follow Share @Verma Ashish it will be $L=\left \{ a^{1}b^{1}\cup a^{2} b^{1}\cup a^{3}b^{1}\cup .......\cup a^{2}b^{2}........\infty\right \}$ 1 votes 1 votes Verma Ashish commented May 27, 2019 reply Follow Share Yes. $\epsilon$ also included. But how it will be cSL or CFL? 0 votes 0 votes srestha commented May 27, 2019 reply Follow Share $a$ and $b$ dependent here. So, cannot be regular.:) 0 votes 0 votes Sanandan commented Oct 3, 2020 reply Follow Share Option C , both are regular. 0 votes 0 votes Shiva Sagar Rao commented Apr 27, 2021 reply Follow Share https://gateoverflow.in/261354/madeeasy-test-series-theory-computation-regular-languages 0 votes 0 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes We can drow a dfa for s1 and s2 .so both are regular. abhishekmehta4u answered May 27, 2019 selected May 27, 2019 by srestha abhishekmehta4u comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments yuviabhi commented Jun 17, 2019 reply Follow Share S2 : {a^nb^n | n>=1} U {a^nb^m | n>=1, m>=1} S2 : DCFL U REGULAR S2 : DCFL Is it correct ? 0 votes 0 votes srestha commented Jun 17, 2019 reply Follow Share yes correct, but more likely,it will be regular as it is $a^{*}b^{*}$ 0 votes 0 votes yuviabhi commented Jun 17, 2019 reply Follow Share S2 is a*b* or a+b+ ? 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes $ ((a)^{n})^{m} $ can be rewritten as $ ((a)^{1})^{nm} $ Actually the reasoning should be the other way around $ (a)^{k} = (a^{1})^{k} = (a^{1})^{mn} = L ~ ~\forall k \in \mathbb{N} $ This language is obviously regular. Language 2 is the union of L1 and L2 where L1 $\subset$ L2 and L2 is regular. Hence L1 $\cup$ L2=L2, which is regular. Joey answered Jan 3, 2021 edited Sep 25, 2022 by Joey Joey comment Share Follow See all 2 Comments See all 2 2 Comments reply Saran12 commented Sep 24, 2022 reply Follow Share @JoeyS2 is not a union of 2 Regular languages.{a^nb^n |n>=1} is not regular 0 votes 0 votes Joey commented Sep 25, 2022 reply Follow Share Yeah, sorry about that. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes option C becuase L1={ epsilon , a,a2,a3 ,a3 ,a4...............}where all are in power of a means L1=a* so it is regular. L={a1b1∪a2b1∪a3b1∪.......∪a2b2........∞} so L2=a^nb^m so it is also regular. Bikki_gupta answered May 27, 2019 Bikki_gupta comment Share Follow See all 0 reply Please log in or register to add a comment.