retagged by
281 views
2 votes
2 votes

$X$ and $Y$ are two sets of strings from  $\Sigma^*.$ Assume that $Y\subseteq X.$

Which of the following statements must ALWAYS be true for $X$and $Y?$

  1. If $X$ is finite then $Y$ is finite.
  2. If $X$ is regular then $Y$ is regular.
  3. If $X$ is context-free, then $Y$ is context-free.
  1. I only
  2. II only
  3. III only
  4. I, II & III
retagged by

1 Answer

Best answer
4 votes
4 votes
Any subset of a finite set will be finite, but it is possible to have a subset of regular language which is not regular or a subset of CFL which is not CFL. For example language describing the halting problem is not recursive but is a proper subset of $\Sigma^*.$ which is regular and hence CFL too.
selected by
Answer:

Related questions

2 votes
2 votes
1 answer
2
0 votes
0 votes
1 answer
4
Bikram asked Feb 9, 2017
308 views
Consider the grammar:$S\rightarrow$ $PQ | SQ | PS$$P\rightarrow k$$Q\rightarrow m$To get a set of $n$ terminals, the number of productions to be used are ______. $n^{2...