Regular languages and finite automata
Question 1 |
Let L be a regular language and M be a context-free language, both over the alphabet Σ. Let Lc and Mc denote the complements of L and M respectively. Which of the following statements about the language if Lc ∪ Mc is TRUE?
It is necessarily regular but not necessarily context-free. | |
It is necessarily context-free. | |
It is necessarily non-regular. | |
None of the above. |
Question 1 Explanation:
Context-free languages not closed under complementation. So, Lc ∪ Mc is neither regular nor context-free. It might be context sensitive language.
Question 2 |
Which of the following statements is TRUE about the regular expression 01*0?
It represents a finite set of finite strings. | |
It represents an infinite set of finite strings. | |
It represents a finite set of infinite strings. | |
It represents an infinite set of infinite strings. |
Question 2 Explanation:
The given expression 01*0 is regular. So this is a finite string. So options C and D are false and * is placed. So this is infinite set.
So, given regular expression represents an infinite set of finite strings.
So, given regular expression represents an infinite set of finite strings.