Question
Download Solution PDFConsider the following problems. L(๐บ) denotes the language generated by a grammar ๐บ. L(๐) denotes the language accepted by a machine ๐.
(I) For an unrestricted grammar ๐บ and a string ๐ค, whether ๐ค ∈ (๐บ)
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammars ๐บ1 and ๐บ2, whether (๐บ1) = (๐บ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?
Answer (Detailed Solution Below)
Detailed Solution
Download Solution PDFMembership algorithm does not exist for unrestricted grammars.
Regularity problem for TM is undecidable.
Equivalence of Two grammar is undecidable.
Every NFA is a PDA with a finite memory.
Last updated on Jan 8, 2025
-> GATE CS 2025 Admit Card has been released on 7th January 2025.
-> The exam will be conducted on 1st February 2025 in 2 shifts.
-> Candidates applying for the GATE CE must satisfy the GATE Eligibility Criteria.
-> The candidates should have BTech (Computer Science). Candidates preparing for the exam can refer to the GATE CS Important Questions to improve their preparation.
-> Candidates must check their performance with the help of the GATE CS mock tests and GATE CS previous year papers for the GATE 2025 Exam.