2 votes 2 votes Consider the language $\textsf{Pal}$ consisting of all palindromes over alphabet $\Sigma=\{0\}.$ Which of the following statements is/are False? $\textsf{Pal}$ is non-regular. Every infinite subset of $\textsf{Pal}$ is non-regular. Every infinite superset of $\textsf{Pal}$ is regular. Every finite subset of $\textsf{Pal}$ is regular. Theory of Computation goclasses2024-toc-1-weekly-quiz goclasses theory-of-computation regular-language multiple-selects 2-marks + – GO Classes asked Jun 9, 2022 retagged Jun 17, 2023 by Lakshman Bhaiya GO Classes 411 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply samarpita commented Jun 10, 2022 reply Follow Share @Deepak Poonia @Sachin Mittal 1 sir in option B if we consider the example L={0^2n} ,then it will be regular….so “it is always not regular”,this is false 0 votes 0 votes Arjun commented Jun 10, 2022 reply Follow Share Thats marked as false itself in answer key right? 2 votes 2 votes samarpita commented Jun 10, 2022 reply Follow Share @Arjun ok sir 0 votes 0 votes Please log in or register to add a comment.
12 votes 12 votes Option C: the tricky word is “superset” Adding anything to $\sum$* makes no sense right !. So, Every infinite superset of $\sum$* is regular again. Udhay_Brahmi answered Jun 20, 2022 Udhay_Brahmi comment Share Follow See 1 comment See all 1 1 comment reply Deepak Poonia commented Jun 26, 2022 reply Follow Share I appreciate that you put comment for things you find tricky or worth pointing out. This habit helps ourselves in long run, after few months, when we revisit same question, 7 votes 7 votes Please log in or register to add a comment.
2 votes 2 votes Pal is regular because the input alphabet set is $\{0\}$, so, $\mathrm{Pal}=\Sigma^{\ast }=0^{\ast }$. Consider the infinite subset $0^{\text {prime }}$ of pal, it is non-regular and the infinite superset $\Sigma^{\ast }$ of pal is pal itself so it is regular. Every finite language is always regular. GO Classes answered Jun 9, 2022 GO Classes comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes NOTE:- Palindromes over Unary language are always regular …. So , option A ,B are false. while in C, superset/subset of regular language is also regular, so, it’s true. MANSI_SOMANI answered Sep 2, 2022 MANSI_SOMANI comment Share Follow See all 2 Comments See all 2 2 Comments reply Pragti1200 commented Sep 11, 2022 reply Follow Share is it always true that “superset/subset of regular language is also regular”? 0 votes 0 votes MANSI_SOMANI commented Sep 11, 2022 reply Follow Share @Pragti1200 it's true for the example given in the question as it's unary! 0 votes 0 votes Please log in or register to add a comment.