Exams › GATE › Technical

Consider the pushdown automaton (PDA) P below, which runs on the input alphabet {a,b}, has stack alphabet {⊥,A}, and has three states {s,p,q}, with s being the start state. A transition from state u to state v, labelled c/X/γ, where c is an input symbol or ε, X is a stack symbol, and γ is a string of stack symbols, represents the fact that in state u, the PDA can read c from the input, with X on the top of its stack, pop X from the stack, push in the string γ on the stack, and go to state v. In the initial configuration, the stack has only the symbol ⊥ in it. The PDA accepts by empty stack. Which one of the following options correctly describes the language accepted by P?

1. {a^m bⁿ | 1 ≤ m and n < m}
2. {a^m bⁿ | 0 ≤ n ≤ m}
3. {a^m bⁿ | 0 ≤ m and 0 ≤ n}
4. {a^m | 0 < m} ∪ {bⁿ | 0 < n}

Correct answer: {a^m bⁿ | 0 ≤ n ≤ m}

Solution

The correct option describes a language where the number of 'b's can be equal to or less than the number of 'a's, which aligns with the PDA's ability to push and pop symbols based on the input, ensuring that for every 'b' processed, there is a corresponding 'a' that can be matched, thus maintaining the condition 0 ≤ n ≤ m.

Related GATE Technical questions

• Which one of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
• Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?
• Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet {0,1}, and has the set of states {s,p,q,r}, with s being the start state and p being the only final state. Which one of the following regular expressions correctly describes the language accepted by A?
• Which one of the options given below refers to the degree (or arity) of a relation in relational database systems?
• Suppose two hosts are connected by a point-to-point link and they are configured to use Stop-and-Wait protocol for reliable data transfer. Identify in which one of the following scenarios, the utilization of the link is the lowest.
• An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let k be the number of keys, m be the number of slots in the hash table, and k > m. Which one of the following is the best hashing strategy to counteract the adversary?

⚔️ Practice GATE Technical free + battle 1v1 →