CS21 Decidability and Tractability
Lecture 6 January 17, 2024
Context-free grammars and languages
• languages recognized by a (N)FA are exactly the languages described by regular expressions, and they are called the regular languages
Copyright By PowCoder代写 加微信 powcoder
• languages recognized by a NPDA are exactly the languages described by context-free grammars, and they are called the context-free languages
January 17, 2024 CS21 Lecture 6 2
January 17, 2024
CS21 Lecture 6
Context-Free Grammars
start symbol
A → 0A1 A→B B→#
terminal symbols
non-terminal symbols
production
Context-Free Grammars
• generate strings by repeated replacement of non-terminals with string of terminals and non-terminals
– write down start symbol (non-terminal)
– replace a non-terminal with the right-hand- side of a rule that has that non-terminal as its left-hand-side.
– repeat above until no more non-terminals
January 17, 2024 CS21 Lecture 6 4
Context-Free Grammars
A ⇒ 0A1 ⇒ 00A11 ⇒
000A111 ⇒ 000B111 ⇒
• a derivation of the string 000#111
• set of all strings generated in this way is
the language of the grammar L(G)
• called a Context-Free Language
January 17, 2024 CS21 Lecture 6 5
A → 0A1 A→B B→#
Context-Free Grammars
• Naturallanguages(e.g.English) structure:
January 17, 2024 CS21 Lecture 6
hasvheotrhthisansdorftoorf multiple rules with same lhs
Generate a string in
the language of this grammar.
Context-Free Grammars
• CFGs don’t capture natural languages completely
• computer languages often defined by CFG
– hierarchical structure
– slightly different notation often used “Backus- Naur form”
– see next slide for example
January 17, 2024 CS21 Lecture 6 7
Example CFG
|
| (
→ a | b | c | … | x | y | z
January 17, 2024 CS21 Lecture 6 8
CFG formal definition • Acontext-freegrammarisa4-tuple
(V, Σ, R, S)
– V is a finite set called the non-terminals
– Σ is a finite set (disjoint from V) called the terminals
– R is a finite set of productions where each production
is a non-terminal and a string of terminals and non-
terminals.
– S ∈ V is the start variable (or start non-terminal)
January 17, 2024 CS21 Lecture 6 9
CFG formal definition
• u, v, w are strings of non-terminals and terminals, and A → w is a production:
notation: uAv ⇒ uwv notation: uAv ⇒! uwv
notation: u ⇒” v
– meaning: there exists strings u1,u2,…uk-1 for
which u ⇒!u1 ⇒!u2 ⇒!… ⇒!uk-1 ⇒!v
January 17, 2024 CS21 Lecture 6 10
“uAv yields uwv” also: “yields in 1 step”
• in general:
“yields in k steps”
CFG formal definition
• notation: u ⇒∗v
– meaning: ∃ k ≥ 0 and strings u1,…,uk-1 for
which u ⇒!u1 ⇒!u2 ⇒!… ⇒!uk-1 ⇒!v
• if u = start symbol, this is a derivation of v • The language of G, denoted L(G) is:
{w∈Σ*:S⇒∗ w}
January 17, 2024 CS21 Lecture 6 11
CFG example
• Balanced parentheses:
–() –(()((()())))
• astringwinΣ*={(,)}*isbalancediff: – # “(”s equals # “)”s, and
–forany prefixofw,#“(”s ≥#“)”s
Exercise: design a CFG for balanced parentheses. January 17, 2024 CS21 Lecture 6 12
CFG example
S → (S) | SS | 𝜖
• Proof that w ∈ L(G) implies w is balanced – induction on length of derivation
– base case: length 1: S ⇒ 𝜖
– general case: length n
•S⇒(S)⇒!”# w$ =w • S ⇒ SS ⇒!”# 𝑤$𝑤′′ = w
January 17, 2024 CS21 Lecture 6 13
CFG example
S → (S) | SS | 𝜖
• Proof that w is balanced implies w ∈ L(G)
– induction on length of w
– base case: length 0: w = 𝜖
– general case: length n
– consider shortest prefix in language
– if whole string then w = (w’) and w’ balanced
– if proper prefix then w = w’w’’ with w’ and w’’
January 17, 2024 CS21 Lecture 6 14
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com