1
Question
Consider the following two statements about regular languages:
S1: Every infinite regular language contains an undecidable language as a subset.
S2: Every finite language is regular.
Which one of the following choices is correct?
S1: Every infinite regular language contains an undecidable language as a subset.
S2: Every finite language is regular.
Which one of the following choices is correct?
Open in App
Solution
S1: Every infinite regular language contains an undecidable language as a subset.
S2: Every finite language regular.
Clearly, S2 is true, since for finite language, we can design FA by brute force, with a finte number of states.
Since, any language can be subset of an infinite language (No infinte language is closed under subset operation).
So, an infinite regular language can have any type of language as a subset including undecidable (non-REC) languages.
So, S1 is also true. So, both S1 and S2 are true.
So, option (a) is correct.
S2: Every finite language regular.
Clearly, S2 is true, since for finite language, we can design FA by brute force, with a finte number of states.
Since, any language can be subset of an infinite language (No infinte language is closed under subset operation).
So, an infinite regular language can have any type of language as a subset including undecidable (non-REC) languages.
So, S1 is also true. So, both S1 and S2 are true.
So, option (a) is correct.
Suggest Corrections
0
Join BYJU'S Learning Program
Join BYJU'S Learning Program
