and
In this, we also require that if a = λ, then p j = p l . In other words, the states of
are labeled with pairs (q i , p j ), representing the respective states in which M 1 and
M 2 can be after reading a certain input string. It is a straightforward induction
argument to show that
with q r ε F 1 and P s ε F 2 if and only if
and
Therefore, a string is accepted by if and only if it is accepted by M 1 and M 2 ,
that is, if it is in L (M 1 ) L (M 2 )= L 1 L 2 .
The property addressed by this theorem is called closure under regular
intersection. Because of the result of the theorem, we say that the family of
context-free languages is closed under regular intersection. This closure property
is sometimes useful for simplifying arguments in connection with specific
languages.
Example 8.7
Show that the language
is context-free.
It is possible to prove this claim by constructing a pda or a context-free
In this, we also require that if a = λ, then p j = p l . In other words, the states of
are labeled with pairs (q i , p j ), representing the respective states in which M 1 and
M 2 can be after reading a certain input string. It is a straightforward induction
argument to show that
with q r ε F 1 and P s ε F 2 if and only if
and
Therefore, a string is accepted by if and only if it is accepted by M 1 and M 2 ,
that is, if it is in L (M 1 ) L (M 2 )= L 1 L 2 .
The property addressed by this theorem is called closure under regular
intersection. Because of the result of the theorem, we say that the family of
context-free languages is closed under regular intersection. This closure property
is sometimes useful for simplifying arguments in connection with specific
languages.
Example 8.7
Show that the language
is context-free.
It is possible to prove this claim by constructing a pda or a context-free