743 views

Given the recursively enumerable language $(L_{RE})$, the context sensitive language $(L_{CS})$, the recursive language $(L_{REC})$, the context free language $(L_{CF})$ and deterministic context free language $(L_{DCF})$. The relationship between these families is given by

1. $L_{CF} \subseteq​ L_{DCF} \subseteq​ L_{CS} \subseteq​ L_{RE} \subseteq​ L_{REC}$
2. $L_{CF} \subseteq​ L_{DCF} \subseteq​ L_{CS} \subseteq​ L_{REC} \subseteq​ L_{RE}$
3. $L_{DCF} \subseteq​ L_{CF} \subseteq​ L_{CS} \subseteq​ L_{RE} \subseteq​ L_{REC}$
4. $L_{DCF} \subseteq​ L_{CF} \subseteq​ L_{CS} \subseteq​ L_{REC} \subseteq​ L_{RE}$

recategorized | 743 views