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.
Asked
Active
Viewed 1,148 times
4
-
Patterns in the class of regular languages are less restricted than non-regular languages (CFLs, CSLs). my answer to another question may help ... – Grijesh Chauhan Mar 31 '20 at 07:02
2 Answers
18
@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.
rici
- 12,020
- 21
- 38
-
Actually I had the same in mind, just presented a specific example for illustration purposes. – Vladislav Mar 29 '20 at 21:15
-
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. – wberry Mar 30 '20 at 19:15
8
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.
Vladislav
- 687
- 4
- 10