Exams › GATE › Technical
Let G1, G2 be Context Free grammars (CFGs) and R be a regular expression. For a grammar G, let L(G) denote the language generated by G. Which ONE among the following questions is decidable?
(A) Is L(G1) = L(G2)?
(B) Is L(G1) ∩ L(G2) = ∅?
(C) Is L(G1) = L(R)?
(D) Is L(G1) = ∅?
- Is L(G1) = L(G2)?
- Is L(G1) ∩ L(G2) = ∅?
- Is L(G1) = L(R)?
- Is L(G1) = ∅?
Correct answer: Is L(G1) = ∅?
Solution
Determining whether the language generated by a context-free grammar is empty is decidable because there exists an algorithm that can analyze the grammar's production rules to check if any strings can be derived from it.
Related GATE Technical questions
- Which one of the following options is correct for the given data in the table?
Iteration (i): 0, 1, 2, 3
Input (I): 20, -4, 10, 15
Output (X): 20, 16, 26, 41
Output (Y): 20, -80, -800, -12000
- Consider a binary tree T in which every node has either zero or two children. Let n > 0 be the number of nodes in T. Which ONE of the following is the number of nodes in T that have exactly two children?
- Let L, M, and N be non-singular matrices of order 3 satisfying the equations L² = L⁻¹, M = L⁸ and N = L². Which ONE of the following is the value of the determinant of (M - N)?
- Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?
- Consider the following statements:
(i) Address Resolution Protocol (ARP) provides a mapping from an IP address to the corresponding hardware (link-layer) address.
(ii) A single TCP segment from a sender S to a receiver R cannot carry both data from S to R and acknowledgement for a segment from R to S.
Which ONE of the following is CORRECT?
- A machine receives an IPv4 datagram. The protocol field of the IPv4 header has the protocol number of a protocol X. Which ONE of the following is NOT a possible candidate for X?
⚔️ Practice GATE Technical free + battle 1v1 →