243 views
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.

$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

1
301 views