If L1 is a regular language and L2 is a context free language, which of the following statement is correct?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. L1∩L2 is a context free language.
Explanation
It is a standard closure property of context-free languages that the intersection of a context-free language with a regular language is always context-free (proved by a product construction of the CFL's PDA with the regular language's DFA). This intersection need not be regular, and context-free languages in general are not all accepted by a deterministic PDA (only the smaller class of deterministic CFLs is), so option 4 is not guaranteed. Subsets of a context-free union are not guaranteed to be context-free either, since any language whatsoever is a subset of some union. Hence L1∩L2 is context free is the only statement guaranteed to be correct.More Theory of Computation and Compilers questions
- Given the functions: Predecessor function: Pred(x) = x − 1 and T(x, y+1) = Pred(T(x, y)), T(x, 0) = x. Which of the following operations is…
- Arrange the following families of languages from specialization to generalization, defined over alphabet Σ: A. Family of all regular langua…
- Which of the following statements is incorrect?
- The minimum state DFA of the following would be the following: (a DFA with states q0 (start), q1, q2, q3 and q4 (accepting) is given, with…
- Find the Follow (A) & Follow (C).
- In the LL(1) Parsing table of the given CFG, how many valid non-blank entries will be there in the rows for variables 'B' and 'D'?