For a string \(w\), we define \(w^R\) to be the reverse of \(w\). Which of the following languages is/are context-free?
Show Hint
- \( \{\, w x w^R x^R \mid w,x \in \{0,1\}^* \,\} \)
- \( \{\, w w^R x x^R \mid w,x \in \{0,1\}^* \,\} \)
- \( \{\, w x w^R \mid w,x \in \{0,1\}^* \,\} \)
- \( \{\, w x x^R w^R \mid w,x \in \{0,1\}^* \,\} \)
The Correct Option is B, C, D
Solution and Explanation
Step 1: Analyze option (C).
The language \( \{ w x w^R \} \) is context-free since a PDA can push symbols of \(w\), ignore \(x\), and then pop to match \(w^R\). Hence, (C) is context-free.
Step 2: Analyze option (D).
The language \( \{ w x x^R w^R \} \) is a concatenation of two palindromic patterns and can be recognized by a PDA using a stack in two phases. Hence, (D) is context-free.
Step 3: Analyze option (B).
The language \( \{ w w^R x x^R \} \) is a concatenation of two palindromes, each of which is context-free, and CFLs are closed under concatenation. Hence, (B) is context-free.
Step 4: Eliminate option (A).
The language \( \{ w x w^R x^R \} \) requires simultaneous matching of two independent strings in cross order, which is not possible with a single stack PDA. Hence, (A) is not context-free.
Top Questions on Context-free grammars and push-down automata
- Consider the following context-free grammar \(G\), where \(S\), \(A\), and \(B\) are the variables (non-terminals), \(a\) and \(b\) are the terminal symbols, \(S\) is the start variable, and the rules of \(G\) are described as:
\[ S \to aaB \mid Abb \] \[ A \to a \mid AaA \] \[ B \to b \mid bB \] Which ONE of the languages \(L(G)\) is accepted by \(G\)?- GATE CS - 2025
- Theory of Computation
- Context-free grammars and push-down automata
In a pushdown automaton \( P = (Q, \Sigma, \Gamma, \delta, q_0, F) \), a transition of the form
where \( p, q \in Q \), \( a \in \Sigma \cup \{\epsilon\} \), and \( X, Y \in \Gamma \cup \{\epsilon\} \), represents \[ (q, Y) \in \delta(p, a, X). \] Consider the following pushdown automaton over the input alphabet \( \Sigma = \{a, b\} \) and stack alphabet \( \Gamma = \{\#, A\} \):
The number of strings of length 100 accepted by the above pushdown automaton is \(\underline{\hspace{2cm}}\).
- GATE CS - 2021
- Theory of Computation
- Context-free grammars and push-down automata
Questions Asked in GATE CS exam
In the diagram, the lines QR and ST are parallel to each other. The shortest distance between these two lines is half the shortest distance between the point P and the line QR. What is the ratio of the area of the triangle PST to the area of the trapezium SQRT?
Note: The figure shown is representative
- GATE CS - 2025
- Geometry
Consider the following process information for Shortest Remaining Time First (SRTF) scheduling:
\[ \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time (AT)} & \textbf{Burst Time (BT)} \\ \hline P1 & 0 & 10 \\ P2 & 1 & 13 \\ P3 & 2 & 6 \\ P4 & 8 & 9 \\ \hline \end{array} \]Find the turnaround time for each process.
- GATE CS - 2025
- Programming in C
- If IMAGE and FIELD are coded as FHBNJ and EMFJG respectively then, which one among the given options is the most appropriate code for BEACH?
- GATE CS - 2025
- GATE IN - 2025
- GATE MT - 2025
- GATE NM - 2025
- GATE TF - 2025
- Logical and Analytical Reasoning Skills
A square paper, shown in figure (I), is folded along the dotted lines as shown in figures (II) and (III). Then a few cuts are made as shown in figure (IV). Which one of the following patterns will be obtained when the paper is unfolded?
- GATE CS - 2025
- Paper Folding and Cutting
Consider the relationships among P, Q, R, S, and T:
• P is the brother of Q.
• S is the daughter of Q.
• T is the sister of S.
• R is the mother of Q.
The following statements are made based on the relationships given above.
(1) R is the grandmother of S.
(2) P is the uncle of S and T.
(3) R has only one son.
(4) Q has only one daughter.
Which one of the following options is correct?- GATE CS - 2025
- Blood Relations