1
$\begingroup$

A context-free language (CFL) is a language generated by some context-free grammar (CFG).

A regular language (also called a rational language) is a formal language that can be expressed using a regular expression.

Question : Assume that $L_1$ is a context-free language and $L_2$ is a regular language. Is there any algorithm to decide that $L_1 \cap L_2$ is empty or not?

$\endgroup$
0
$\begingroup$

The answer is yes. Given a context-free grammar generating a language $L_1$ and a regular language $L_2$ given by some finite automaton, one can effectively construct a context-free grammar generating the language $L_1 \cap L_2$. Now, given a context-free grammar, one can decide whether the language it generates is empty or not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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