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.8k views answer comment Share Follow See all 18 Comments See all 18 18 Comments reply Show 15 previous comments 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.