# Recent questions tagged context-free-grammars

1
Consider an $\varepsilon$-tree CFG. If for every pair of productions $A\rightarrow u$ and $A\rightarrow v$ If $\text{FIRST(u)} \cap \text{FIRST(v)}$ is empty then the CFG has to be $LL(1).$ If the CFG is $LL(1)$ then $\text{FIRST(u)} \cap \text{FIRST(v)}$ has to be empty. Both $(A)$ and $(B)$ None of the above
2
The CFG $S \to aS\mid bS\mid a\mid b$ is equivalent to $(a+b)$ $(a+b)(a+b)^*$ $(a+b)(a+b)$ all of these
3
Let $G$ be a grammar in CFG and let $W_1,W_2\in L(G)$ such that $\mid W_1\mid=\mid W_2\mid$ then which of the following statements is true? Any derivation of $W_1$ has exactly the same number of steps as any derivation of $W_2$. Different derivation have different length. Some derivation of $W_1$ may be shorter than the derivation of $W_2$ None of the options
4
The grammar $S\rightarrow aSb\mid bSa\mid SS\mid \varepsilon$ is: Unambiguous CFG Ambiguous CFG Not a CFG Deterministic CFG
5
Let $G= (V,T,S,P)$ be a context-free grammer such that every one of its productions is of the form $A\rightarrow v$, with $\mid v \mid=K> 1$. The derivation tree for any $W \in L(G)$ has a height $h$ ... $\log_{K}|W \mid \leq h \leq \left (\frac{ \mid W \mid - 1}{K-1} \right)$
1 vote
6
The language which is generated by the grammar $S \rightarrow aSa \mid bSb \mid a \mid b$ over the alphabet of $\{a,b\}$ is the set of Strings that begin and end with the same symbol All odd and even length palindromes All odd length palindromes All even length palindromes
7
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.
8
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.
9
Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable. (Hint: Use a reduction from $PCP$ ... $a_{1},\dots,a_{k}$ are new terminal symbols. Prove that this reduction works.)
10
Show that $EQ_{CFG}$ is co-Turing-recognizable.
11
Show that $EQ_{CFG}$ is undecidable.
12
Say that a variable $A$ in $CFL\: G$ is usable if it appears in some derivation of some string $w \in G$. Given a $CFG\: G$ and a variable $A$, consider the problem of testing whether $A$ is usable. Formulate this problem as a language and show that it is decidable.
13
Let $C_{CFG} = \{\langle G, k \rangle \mid \text{ G is a CFG and L(G) contains exactly$k$strings where$k \geq 0$or$k = \infty$}\}$. Show that $C_{CFG}$ is decidable.
14
Let $C = \{ \langle G, x \rangle \mid \text{G is a CFG$x$is a substring of some$y \in L(G)$}\}$. Show that $C$ is decidable. (Hint: An elegant solution to this problem uses the decider for $E_{CFG}$.)
15
If we disallow $\epsilon$-rules in CFGs, we can simplify the DK-test. In the simplified test,we only need to check that each of DK’s accept states has a single rule. Prove that a CFG without $\epsilon$-rules passes the simplified DK-test iff it is a DCFG.
16
Let $G_{1}$ be the following grammar that we introduced in Example $2.45$. Use the DK-test to show that $G_{1}$ is not a DCFG. $R \rightarrow S \mid T$ $S \rightarrow aSb \mid ab$ $T \rightarrow aTbb \mid abb$
17
Let G be the following grammar: $S \rightarrow T\dashv$ $T \rightarrow T aT b \mid T bT a | \epsilon$ Show that $L(G) = \{w\dashv \: \mid w\: \text{contains equal numbers of a’s and b’s} \}$. Use a proof by induction on the length of $w$. Use the DK-test to show that G is a DCFG. Describe a DPDA that recognizes L(G).
18
Show that every DCFG generates a prefix-free language.
19
Show that every DCFG is an unambiguous CFG.
20
Let $\Sigma = \{0,1\}$ and let $B$ be the collection of strings that contain at least one $1$ in their second half. In other words, $B = \{uv \mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast}1\Sigma^{\ast}\: \text{and} \mid u \mid \geq \mid v \mid \}$. Give a PDA that recognizes $B$. Give a CFG that generates $B$.
21
Consider the following CFG $G:$ $S \rightarrow SS \mid T$ $T \rightarrow aT b \mid ab$ Describe $L(G)$ and show that $G$ is ambiguous. Give an unambiguous grammar $H$ where $L(H) = L(G)$ and sketch a proof that $H$ is unambiguous.
22
Show how, having filled in the table as in Question $4.4.9$, we can in $O(n)$ time recover a parse tree for $a_{1}a_{2}\cdot\cdot\cdot a_{n}$. Hint: modify the table so it records, for each nonterminal $A$ in each table entry $T_{ij}$, some pair of nonterminals in other table entries that justified putting $A$ in $T_{ij}$.
Every language that has a context-free grammar can be recognized in at most $O(n^{3})$ time for strings of length $n$ ... n_{3})$time. Having filled in the table, how do you determine whether$a_{l}a_{2}\cdot\cdot\cdot a_{n} is in the language?
Design grammars for the following languages: The set of all strings of $0's$ and $1's$ such that every $0$ is immediately followed by at least one $1$. The set of all strings of $0's$ and $1's$ that are palindromes; that is, the string reads the same backward as forward. The set of all ... of all strings of $0's$ and $1's$ of the form $xy$, where $x\neq y$ and $x$ and $y$ are of the same length.
Repeat Question $4.2.1$ for each of the following grammars and strings: $S\rightarrow 0S1\mid 01$ with string $000111$. $S\rightarrow +SS\mid \ast SS\mid a$ with string $+\ast aaa$. $S\rightarrow S(S)S\mid \epsilon$ with string $(()())$ ... $bterm\:\rightarrow\:bterm\:and\:bfactor\mid bfactor$ $bfactor\:\rightarrow\:not\:bfactor\mid (bexpr)\mid true\mid false$