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
- With respect to a TCP connection between a client and a server, which of the following is true?
- GATE CS - 2026
- Computer Networks
- Let $P, Q, R, S$ be relational schemas. Let ``$\rightarrow$'' indicate a functional dependency (FD) in this context. Which of the following best describes the meaning of a functional dependency?
- GATE CS - 2026
- Database Management Systems
- Let a Non-deterministic Finite Automaton (NFA) have 6 states over a finite alphabet. Which of the following cannot be the number of states in a minimal Deterministic Finite Automaton (DFA) that is equivalent to this NFA?
- GATE CS - 2026
- Theory of Computations
- A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?
- GATE CS - 2026
- Computer Organization and Architecture
- Consider $Z = X - Y$, where $X$, $Y$ and $Z$ are all in sign-magnitude form. $X$ and $Y$ are each represented in $n$ bits. To avoid overflow, the representation of $Z$ would require a minimum of:
- GATE CS - 2026
- Computer Organization and Architecture