in Theory of Computation
243 views
0 votes
0 votes
Show that if $L_1$ is deterministic context-free and $L_2$ is regular, then the language $L_1 ∪ L_2$ is
deterministic context-free.
in Theory of Computation
243 views

1 Answer

1 vote
1 vote
$L1 \cup L2 = (L1'\cap L2')'$

Let L1 is DCFL then L1' is also DCFL

Let L2 is Regular then L2' is also Regular

 $L1'\cap L2'$ is DCFL since any language intersection with regular language is always the language

so $(L1'\cap L2')'$ is DCFL as complement of DCFL is DCFL

$L1 \cup L2 $ is DCFL

Related questions