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

Accountable and Legitimate government

Consider the ...

Question

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?

Only

P_{2}

is decidable

No worries! We‘ve got your back. Try BYJU‘S free classes today!

P_{1}

and

P_{2}

are decidable

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

Neither

P_{1}

nor

P_{2}

are decidable

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Only

P_{1}

is decidable

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

The correct option is B $P_{1}$ and $P_{2}$ are decidable
$P_{1}$ is membership of FSM i.e., regular language. $P_{2}$ is finte/infiniteness of context free grammer. Membership of FSM and finiteness of CFG, both are decidable problems.
So $P_{1}$ and $P_{2}$ both are decidable.

Suggest Corrections

Similar questions

S_{1} a n d S_{2}

S_{1}

S_{2}

ω ε

ϕ

\sum^{*}

\sum

ω

ω ε

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______.

P_{1}

P_{2}

P_{1}

P_{2}

Join BYJU'S Learning Program