CS21 Decidability and Tractability
Lecture 9 January 24, 2024
Deciding CFLs
• Convert CFG into Chomsky Normal Form
Copyright By PowCoder代写 加微信 powcoder
• parse tree for string x generated by nonterminal A:
January 24, 2024
IfA→k x (k>1)thentheremust be a way to split x:
• A → BC is a production and
•B→i yandC⇒j zfori,j