Let $N_{f}$ and $N_{p}$ denotes the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata,respectively.Let $D_{f}$ and $D_{p}$ denote the classes of languages accepted by deterministic finite automata and determnistic push-down automata,respectively.Which one of the following is TRUE?

Open in App

Solution

$L_{f} :$ Non-deterministic finite automata.
$L_{p} :$ Non-deterministic push-down automata.
$D_{f} :$ Deterministic finite automata.
$D_{f} :$ Deterministic push down automata
According to "Subset Construction" theorem every language accepted by Non-deterministic-finite automata $(N_{f}$ ) is also accepted by some Deterministic-Finite automata $(D_{f}$ ) so $D_{f}$ = $N_{f}$ .
Deterministic push-down automata $(D_{p}$ ) recognizes the DCFLs which is a proper subset of the language of context-free languages and the non-deterministic push down automata recognizes the context-free languages.
So. $D_{p} \subset N_{p}$ .

Suggest Corrections

Similar questions

L = {w ϵ {0, 1}^{*} ∣ w e n d s w i t h t h e s u b s t r i n g 0110}

R = (a + b)^{*} (a a + b b) (a + b)^{*}

λ

Join BYJU'S Learning Program