Theory of Computation - Context-Free Grammars

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 → aaB | Abb A → a | aA...

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, respectively. Which of the following statement...

Let G = (V, Σ, S, P) be a context-free grammar in Chomsky Normal Form with Σ = {a,b,c} and V containing 10 variable symbols including the start symbol S. The string w = a^30 b^30 c^30 is derivable from S. The number of s...

Identify the language generated by the following grammar, where S is the start variable. S → XY X → aX | a Y → aYb | ε