Codex Wiki
OurBigBook.com
Site
Source code
Chomsky-normal-form derivation length
...
Area of mathematics
Foundations of mathematics
Formal language theory
Context-free language
Context-free grammar
Chomsky normal form
OurBigBook.com
Words: 29
A Chomsky-normal-form parse tree for a word of length
n
≥
1
has
n
terminal productions and
n
−
1
binary productions. Every derivation represented by the tree therefore has exactly
2
n
−
1
steps.
Ancestors
(8)
Chomsky normal form
Context-free grammar
Context-free language
Formal language theory
Foundations of mathematics
Area of mathematics
Mathematics
Home
Incoming links
(1)
Solution