CameraIcon

SearchIcon

MyQuestionIcon

1

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

Consider the ...

Question

Consider the following Problems, $P_{1}$ and $P_{2}$ :

$P_{1}$ : Checking whether a regular grammer is unambiguous.

$P_{2}$ : Checking whether a given context free grammer is ambiguous.

Which of the above problems is (are) decidable?

Open in App

Solution

Regular grammer ambiguity is decidable and therefore checking if regular grammer is unambiguous is also decidable.

However in case of CFGs, ambiguity is undecidable, and therefore the correct option is (b)

Suggest Corrections

thumbs-up

0

Similar questions

Consider three decision problems P₁, P₂, and P₃. It is known that P₁ is decidable and P₂ is undecidable. Which one of the following is TRUE?

Q. Which of the following are decidable?
1. Whether the intersection of two regular languages is infinite
2. Whether a given context-free language is regular
3. Whether two push-down automata accept the same language
4. Whether a given grammer is context-free

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 problems regarding decidability.
I. Given a Turing Machine M, whether L(M) is context free.
II. Given a Non-deterministic PDA P, whether there exists a Deterministic Turing Machine M Such that both P and M accept the same languge.
III. Given a deterministic Turing Machine M, wheather there exists a Non Deterministic PDA P such that both P and M accept the same languge.
IV. Given a regular languge L, whether the complement of L is a DCFL
Which of the above problems are decidable ?

Q. Assume the statements

S_{1} a n d S_{2}

S_{1}

: Given a context free grammer, there exists an algorithm for determining whether L(g) is infinite.

S_{2}

: There exists an algorithm to determine whether two context free grammars generate the same language.
Which of the following is true?

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Human Circulatory system

Watch in App

Join BYJU'S Learning Program

CrossIcon