MyQuestionIcon

1

You visited us 1 times! Enjoying our articles? Unlock Full Access!

Consider the ...

Question

$C o n s i d e r t h e f o l l o w i n g p r o b l e m s o n d e c i d a b i l i t y : 1 . G i v e n a C F G G a n d a s t r i n g ω \in \sum * . d o e s ω b e l o n g s t o L (G) ? 2 . G i v e n a T u n i n g M a c h i n e T, a s t r i n g ω \in \sum * a n d a n i n t e g e r K, d o e s T a c c e p t ω w i t h i n k s t e p s ? 3 . G i v e n a T u n i n g M a c h i n e T, a s t r i n g ω \in \sum * a n d a s t a t e q \in Q (s e t o f s t a t e o f t h e T u n i n g M a c h i n e) . d o e s t h e c o m p u t a t i o n o f T o n ω v i s i t t h e s t a t e q ? T h e t o t a l n u m b e r o f d e i d a b l e p r o b l e m s a r e______.$

Open in App

Solution

$1 i s t h e m e m b e r s h i p p r o b l e m f o r C F L s, f o r w h i c h w e h a v e t h e C Y K a l g o r i t h m, T h e r e f o r e d e c i d a b l e . 2 i s d e c i d a b l e b e c a u s e w e c a n s i m u l a t e t h e T u n i n g M a c h i n e T o n ω f o r k s t e p s a n d c h e c k w h e t h e r T c o m e s t o a h a l t o r n o t . T h e r e f o r e 2 i s d e c i d a b l e . 3 i s t h e w e l l k n o w n s t a t e e n t r y p r o b l e m, w h i c h i s u n d e c i d a b l e .$

Suggest Corrections

thumbs-up

0

Similar questions

Q. Consider the following decision problems:

P_{1}

: Does a given finte state machine accept a given string

P_{2}

: Does a given context free grammer generate an infinite number of strings.
Which of the following statement is true?

Q. Consider the following Problem X.
"Given a Turing machine M over the input alphabet

\sum

. any state q of M and a word

\sum^{*}

, does the computation of M on w visit the state q"
Which of the following statements about X is correct?

Q. Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M.
Which of the following decision problems are undecidable?
I. Given a regular expression R and a string w,is

ω ε

L(R)?
II. Given a context-free grammar G, is L(G)=

ϕ

III. Given a context-free grammar G, is L(G) =

\sum^{*}

for some alphabet

\sum

?
IV. Given a Turing machine M and a string

ω

ω ε

Q. Which of the following decision problems are undescidable?

I. Given NFAs

N_{1}

N_{2}

L (N_{1}) \cap L (N_{2}) = ϕ

II. Given a CFG G = (N,

\sum

, P, S) and a string

x ϵ \sum^{*},

x ϵ L (G)

?

III. Given CFGs

G_{1} a n d G_{2}

L (G_{1}) = L (G_{2})

?

IV. Given a TM M, is

L (M) = ϕ

Q. 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},

(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?

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Human Resources

Watch in App

Join BYJU'S Learning Program

CrossIcon