Context-Free Grammar

Consider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols. $$ S \rightarrow a S b S|b S| \in $$ Which of the following statements is/are tr...

Given a Context-Free Grammar G as follows: S→Aa | bAc | dc | bda A→d Which ONE of the following statements is TRUE?

Consider the following context-free grammar $G$, where $S, A$, and $B$ are the variables (nonterminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the ru...

Consider a context-free grammar G with the following 3 rules. S → aS, S → aSbS, S → c Let w ∈ L(G). Let n_a(w), n_b(w), n_c(w) denote the number of times a, b, c occur in w, respec...

Consider a context-free grammar $G$ with the following 3 rules. $S \rightarrow aS, \ S \rightarrow aSbS, S \rightarrow c$ Let $w \in L(G)$. Let $n_a(w)$, $n_b(w)$, $n_c(w)$ denote...

Consider the context-free grammar G below $$\matrix{ S & \to & {aSb|X} \cr X & \to & {aX|Xb|a|b,} \cr } $$ where S and X are non-terminals, and a and b are terminal symbols. The st...

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine...

Consider the following context-free grammars: $$\eqalign{ & {G_1}:\,\,\,\,\,S \to aS|B,\,\,B \to b|bB \cr & {G_2}:\,\,\,\,\,S \to aA|bB,\,\,A \to aA|B|\varepsilon ,\,\,B \to bB|\va...

Which one of the following problems is un-decidable?

Match the following List-$${\rm I}$$ with List - $${\rm II}$$ List-$${\rm I}$$ $$E)$$ Checking that identifiers are declared before their $$F)$$ Number of formal parameters in the...

Which one of the following grammars generates the following language? $$L = \left( {{a^i}{b^j}|i \ne j} \right)$$

Which of the following grammar rules violate the requirements of an operator grammar ? $$P,$$ $$Q, R$$ are non-terminals and $$r, s, t$$ are terminals. $$$\eqalign{ & 1)\,\,\,P \to...

Consider the following decision problems : $${P_1}$$ Does a given finite state machine accept a given string $${P_2}$$ Does a given context free grammar generate an infinite number...

Which one of the following is not decidable?

Which of the following definitions below generates the same language as $$L$$ Where $$L = {\left\{ x \right.^n}{y^n}\left| {n \ge \left. 1 \right\}} \right.$$ i) $$\,\,E \to xEy\le...

If $$G$$ is a context-free grammar and $$w$$ is a string of length $$n$$ in $$L(G),$$ how long is a derivation of $$w$$ in $$G,$$ if $$G$$ is Chomsky normal form?