gen-define-a-context-free-grammar-in-language-and-give-one-short-3262

Define a context-free grammar in language and give one short worked example.

# Context-Free Grammar (CFG) ## Definition A **context-free grammar** is a formal grammar defined by a 4-tuple **G = (V, Σ, R, S)** where: - **V** = finite set of *non-terminal* symbols (variables) - **Σ** = finite set of *terminal* symbols (alphabet) - **R** = finite set of *production rules* of the form **A → α** - where A ∈ V (a single non-terminal) - and α ∈ (V ∪ Σ)* (a string of terminals and/or non-terminals) - **S** = start symbol (S ∈ V) --- ## Worked Example **Grammar for balanced parentheses:** - **V** = {S} - **Σ** = {(, )} - **S** = S (start symbol) - **R** = Production rules: 1. S → (S) 2. S → SS 3. S → ε (empty string) ### Derivation of the string "(())" ``` S ⇒ (S) [using rule 1] ⇒ ((S)) [using rule 1] ⇒ (()) [using rule 3: S → ε] ``` This shows **(())** is in the language generated by this grammar. The language generated is **L(G) = {all strings of balanced parentheses}**, such as ε, (), (()), ()(), (()()), etc.