Context free grammars Flashcards
What is the formal model used to recognize context-free languages?
Pushdown Automata.
How does the hierarchy of languages progress from least to most expressive?
Regular ⊂ Context-Free ⊂ Semi-Decidable.
What is the purpose of context-free grammars (CFGs)?
To define languages with hierarchical or nested structures that regular languages can’t describe.
What is an example of a CFG rule set for simple English-like sentences?
S → P V P, P → D N, N → A N, D → a | the, V → holds | eats | observes, N → penguin | balloon, A → happy | little
Give an example sentence that a CFG might generate.
the happy penguin holds a balloon
What is the formal definition of a context-free grammar (CFG)?
A 4-tuple G = (Σ, V, R, S), where Σ is the terminal alphabet, V is a set of non-terminals, R is a set of production rules, and S is the start symbol.
What does the symbol Σ represent in a CFG?
The terminal alphabet (actual symbols in the language).
What does the set V represent in a CFG?
The non-terminal symbols used for generating structure.
What is the role of R in a CFG?
The set of production rules (e.g., A → α).
What does the symbol S represent in a CFG?
The start symbol (a non-terminal from which derivations begin).
What is meant by a one-step derivation in a CFG?
A string u derives v (u ⇒ v) by applying a single production rule.
What does u ⇒* v mean in CFGs?
v can be derived from u in zero or more steps.
What is L(G) in the context of CFGs?
The language generated by grammar G: all strings derivable from S using the rules in R.
What is a context-free language (CFL)?
A language for which there exists a CFG such that L = L(G).
Can regular languages be generated by CFGs?
Yes, every regular language is also context-free.
Can all context-free languages be recognized by finite automata?
No — some context-free languages are not regular.
Give an example of a CFG that generates a regular language.
S → AB, A → aA | ε, B → bB | ε — generates aⁿbᵐ for n, m ≥ 0
Give an example of a CFG that generates a non-regular language.
S → aSb | ε — generates aⁿbⁿ for n ≥ 0
What kind of structure does the CFG S → aSb | ε capture?
Balanced a’s and b’s — matching counts in order.
Give an example of a CFG that generates balanced brackets.
S → SS | (S) | ε
What language does the grammar S → aSc | T | ε
T → Tb | ε generate?
What kind of languages do CFGs excel at describing?
Languages with balanced, nested, or hierarchical patterns.
Why can’t some languages like aⁿbⁿ be expressed using DFAs?
Because DFAs can’t remember how many a’s to match with b’s — they lack memory.
