retagged by
411 views
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?

  1. $\textsf{Pal}$ is non-regular.
  2. Every infinite subset of $\textsf{Pal}$ is non-regular.
  3. Every infinite superset of $\textsf{Pal}$ is regular.
  4. Every finite subset of $\textsf{Pal}$ is regular.
retagged by

3 Answers

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.

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.
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.
Answer:

Related questions

2 votes
2 votes
1 answer
1
2 votes
2 votes
2 answers
3