Consider the following problems L(G) denotes the language generated by a grammar G.L(M) denotes the language accepted by a machine M.
I. For an unrestricted grammar G and a string w, whether w $ϵ$ L(G).
II. Given a Turing Machine M, whether L(M) is regular.
III. Given two grammars $G_{1} a n d G_{2},$ whether L $(G_{1}) = L (G_{2})$ .
IV. Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language.
Which one of the following statements is correct?

Open in App

Solution

I. Membership problem for RE $\to$ undecidable
II. Regularity problem for RE $\to$ undecidable
III. Equivalence problem for RE $\to$ undecidable
IV. Since DPDA P exists for every NFA N and equivalent to it,this problem is trivially decidable.

Suggest Corrections

Similar questions

ω ε

ϕ

\sum^{*}

\sum

ω

ω ε

S_{1} a n d S_{2}

S_{1}

S_{2}

C o n s i d e r t h e f o l l o w i n g N F A M, o v e r t h e a l p h a b e t a . L e t L M b e t h e l a n g u a g e a c c e p t e d b y t h e N F A M . L e t M d e n o t e t h e m a c h i n e o b t a i n e d b y t h e f i n a l a n d n o n f i n a l s t a t e s r e s p e c t i v e l y . T h e n w h i c h o f t h e f o l l o w i n g s t a t e m e n t s i s t r u e a b o u t L M a n d L M ?

S \to b S | a A | b

A \to b A | a B

B \to b B | a S | a

N_{a} (w) a n d

N_{b} (w)

\subseteq

^{+}

Join BYJU'S Learning Program