in Theory of Computation
29 views
0 votes
0 votes
It has been told in Peter Linz that  if L1 is deterministic context-free and L2 is regular, then

             a) the language L1 ∪ L2 is deterministic context-free

             b) the language L1 ∩ L2 is deterministic context-free.

But DCFL is not closed under intersection and union,and every regular language is a DCFL then automatically , therefore L1UL2 and

L1 ∩ L2 might not be closed.

Can anyone please verify?
in Theory of Computation
by
73 points
29 views

1 Answer

0 votes
0 votes

$L_1 \cap L_2 \text{will always be closed under intersection}$

Below explanation is not a proof

Since $L_2$ is a regular language then we can design a $\text{Deterministic Finite Automaton for}$ $L_2.$ The definition of Deterministic PDA$\text{(DPDA)}$ states that every move must be deterministic will the 2 conditions -

  1. $\text{There must be at most one move for any symbol from a state.}$
  2. $\text{If } \delta(q, \lambda, x) \neq \phi \text{ then } \delta(q, a, x) \text{ must be empty for } \forall a \in \Sigma$

which means that $\text{DPDA}$ at least a powerful as any $\text{FA}$ and any regular language can also be realized using $\text{DPDA}$. Now apart from this DFA also has capability of stack which outperform the capability of $\text{DPDA}$ than $\text{FA}$.

$\text{So }\textbf{DCFL}$$ \cap$ $\textbf{Regular Language } \text{will always be closed under intersection}$

by
477 points
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.