4
$\begingroup$

If $L$ is not regular and $ L \subset L_1$, does it follow that $L_1$ is not regular also? Can you please provide an explanation? Thanks in advance.

$\endgroup$
1
  • $\begingroup$ Patterns in the class of regular languages are less restricted than non-regular languages (CFLs, CSLs). my answer to another question may help ... $\endgroup$ Mar 31, 2020 at 7:02

2 Answers 2

18
$\begingroup$

@Vladislav's answer is probably more interesting, but observe that every language over an alphabet $\Sigma$ is a subset of $\Sigma^*$, which is certainly a regular language.

$\endgroup$
2
  • $\begingroup$ Actually I had the same in mind, just presented a specific example for illustration purposes. $\endgroup$
    – Vladislav
    Mar 29, 2020 at 21:15
  • $\begingroup$ This is the most elegant and definitive answer possible. A machine that accepts any input certainly accepts a regular language, of which all others on the same alphabet are proper subsets. $\endgroup$
    – wberry
    Mar 30, 2020 at 19:15
8
$\begingroup$

No. Let $L$ be the language of balanced bracket sequences, and $L_1$ be the language of arbitrary bracket sequences. Then $L \subset L_1$, $L$ is not regular (you can prove it using pumping lemma), but $L_1$ is clearly regular.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.