MyQuestionIcon

1

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

Closure properties of CFL Part - 2

Assume the st...

Question

Assume the statements $S_{1} a n d S_{2}$ given as:
$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?

Open in App

Solution

The proof of $S_{1}$ can be seen in various book of theory category undecidable so a contradiction to this assumption

Suggest Corrections

thumbs-up

0

Similar questions

Q. Which of the following statements are TRUE?

1. The problem of determining whether there exists a cycle in an undirected graph is in P.

2. The problem of determining whether there exists a cycle in an undirected graph is in NP.

3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

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

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

ω

ω ε

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Closure Properties of CFL Part - 2

OTHER

Watch in App

explore_more_icon

Explore more

Closure properties of CFL Part - 2

Join BYJU'S Learning Program

CrossIcon