Exams › GATE › Technical

Consider the transition diagram of a PDA given below with input alphabet Σ = {a,b} and stack alphabet Γ = {X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA. Which one of the following is TRUE?

1. L = {aⁿ bⁿ | n ≥ 0} and is not accepted by any finite automata
2. L = {aⁿ | n ≥ 0} ∪ {aⁿ bⁿ | n ≥ 0} and is not accepted by any deterministic PDA
3. L is not accepted by any Turing machine that halts on every input
4. L = {aⁿ | n ≥ 0} ∪ {aⁿ bⁿ | n ≥ 0} and is deterministic context-free

Correct answer: L = {aⁿ | n ≥ 0} ∪ {aⁿ bⁿ | n ≥ 0} and is deterministic context-free

Solution

The correct option accurately describes the language accepted by the PDA as a union of two sets: strings of 'a's of any length and strings of 'a's followed by an equal number of 'b's. This language can be recognized by a deterministic pushdown automaton, confirming its classification as deterministic context-free.

Related GATE Technical questions

• We want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip-flops required to implement this counter is
• A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?
• Consider the following C program. void f(int, short); void main() { int i = 100; short s = 12; short *p = &s; ________; // call to f() } Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?
• The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
• Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change
• Consider the following C program. #include<stdio.h> void mystery(int *ptra, int *ptrb) { int *temp; temp = ptrb; ptrb = ptra; ptra = temp; } int main() { int a=2016, b=0, c=4, d=42; mystery(&a, &b); if (a < c) mystery(&c, &a); mystery(&a, &d); printf("%d ", a); } The output of the program is _________.

⚔️ Practice GATE Technical free + battle 1v1 →