GATE CSE 2023
Q41.
Consider the pushdown automaton (PDA) P below, which runs on the input alphabet \{a,b\}, has stack alphabet \{ \perp ,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/\gamma , where c is an input symbol or , X is a stack symbol, and \gamma 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 \gamma on the stack, and go to state v. In the initial configuration, the stack has only the symbol \perp in it. The PDA accepts by empty stack.Which one of the following options correctly describes the language accepted by P?Q42.
Geetha has a conjecture about integers, which is of the form\forall x\left [P(x)\Rightarrow \exists yQ(x,y) \right ] where P is a statement about integers, and Q is a statement about pairs of integers. Which of the following (one or more) option(s) would imply Geetha's conjecture?Q43.
Consider a sequence a of elements a_0 = 1, a_1 = 5, a_2 = 7, a_3 = 8, a_4 = 9, \; and \; a_5 = 2. The following operations are performed on a stack S and a queue Q, both of which are initially empty. I: push the elements of a from a_0 to a_5 in that order into S. II: enqueue the elements of a from a_0 to a_5 in that order into Q. III: pop an element from S. IV: dequeue an element from Q. V: pop an element from S. VI: dequeue an element from Q. VII: dequeue an element from Q and push the same element into S. VIII: Repeat operation VII three times. IX: pop an element from S. X: pop an element from S. The top element of S after executing the above operations is ___.Q44.
Which one of the options given below refers to the degree (or arity) of a relation in relational database systems?Q45.
Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: letter \rightarrow [A-Za-z] digit \rightarrow [0-9] id \rightarrow letter (letter\;| \;digit)^* Which one of the following Non-deterministic Finite-state Automata with - transitions accepts the set of valid identifiers? (A double-circle denotes a final state)Q46.
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?Q47.
Let X be a set and 2^X denote the powerset of X. Define a binary operation \Delta on 2^X as follows:A \Delta B=(A-B) \cup (B-A) Let H=(2^X,\Delta ) . Which of the following statements about H is/are correct?Q48.
Consider the control flow graph shown. Which one of the following choices correctly lists the set of live variables at the exit point of each basic block?Q49.
Consider the syntax directed translation given by the following grammar and semantic rules. Here N, I, F \; and \; B are non-terminals. N is the starting non-terminal, and \#,0 \; and \; 1 are lexical tokens corresponding to input letters "\#","0" \; and \; "1", respectively. X.val denotes the synthesized attribute (a numeric value) associated with a non-terminal X. I_1 and F_1 denote occurrences of I and F on the right hand side of a production, respectively. For the tokens 0 and 1, 0.val=0 and 1.val=1.The value computed by the translation scheme for the input string\begin{aligned} N & \rightarrow I \# F & N.val=I.val+F.val \\ I &\rightarrow I_1B & I.val = (2 I1.val) + B.val\\ I &\rightarrow B&I.val = B.val\\ F &\rightarrow BF_1& F.val = \frac{1}{2}(B.val + F1.val)\\ F &\rightarrow B& F.val = \frac{1}{2} B.val\\ B&\rightarrow 0& B.val = 0.val\\ B &\rightarrow 1&B.val = 1.val \end{aligned} 10\# 011is ____ (Rounded off to three decimal places)Q50.
Consider the following table named Student in a relational database. The primary key of this table is rollNum.\begin{array}{|c|c|c|c|} \hline \\ rollNum&name&gender&marks \\ \hline 1&Naman&M&62\\ \hline 2&Aliya&F&70 \\ \hline 3&Aliya &F&80 \\ \hline 4&James&M&82\\ \hline 5&Swati&F&65\\ \hline \end{array} The SQL query below is executed on this database. SELECT * FROM Student WHERE gender = 'F' AND marks > 65; The number of rows returned by the query is ______