Can You Minimize Production Rules in Chomsky Normal Form?

In summary, the conversation discusses the proof of converting a context-free grammar without lambda productions or unit productions to an equivalent grammar in Chomsky Normal Form with a limited number of production rules. The maximum number of symbols on the right side of any production is denoted as "k", and the goal is to show that the equivalent grammar in CNF will have no more than (k-1)|P| + |T| production rules. The poster mentions that there is not much information available on this specific proof and suggests considering the limited form of productions in CNF (A -> BC or A -> a) as a factor. They also question whether the proof should be constructive or inductive.
  • #1
twoski
181
2

Homework Statement



Grammar 'G' is any context-free grammar without any λ productions or unit productions. Let k be the max number of symbols on the right side of any production in P. Prove that there's an equivalent grammar in Chomsky Normal Form with no more than (k − 1)|P| + |T| production rules.

The Attempt at a Solution



There isn't a single similar proof to this anywhere on the internet. There are a lot of basic proofs like proving any CFG can be converted to CNF but nothing this involved.

None of the proofs in my textbook involve minimizing production rules either. Productions in CNF can only be like A -> BC or A- > a, so this would be a factor. I don't know what else to do, should this proof be constructive or inductive?
 
Physics news on Phys.org
  • #2
Thanks for the post! Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?
 

Related to Can You Minimize Production Rules in Chomsky Normal Form?

1. What is Chomsky Normal Form (CNF)?

Chomsky Normal Form, also known as Chomsky's Hierarchy, is a way of representing a formal grammar in a specific form. It was developed by linguist Noam Chomsky in the 1950s as a way of categorizing languages by their grammatical complexity.

2. Why is CNF important in formal language theory?

CNF is important because it allows us to analyze and compare the complexity of different languages. It also helps in developing algorithms for parsing and generating sentences in languages. In addition, many proof techniques in formal language theory rely on the use of CNF.

3. What is the process for converting a grammar into CNF?

The process of converting a grammar into CNF involves several steps. First, we eliminate all productions with more than two non-terminals on the right-hand side. Then, we eliminate epsilon productions by replacing them with new productions. Next, we eliminate unit productions by replacing them with their corresponding productions. Finally, we convert the remaining productions into binary form by splitting up any string of three or more terminals or non-terminals into smaller strings.

4. How can we prove that a grammar is in CNF?

To prove that a grammar is in CNF, we need to show that it satisfies the following conditions: 1) All productions are in the form of A → BC or A → a, where A, B, and C are non-terminals and a is a terminal, 2) The start symbol appears only on the left-hand side of a production, and 3) There are no epsilon or unit productions in the grammar.

5. What is the significance of CNF in the study of formal languages?

CNF is significant in the study of formal languages because it allows us to classify the complexity of languages and determine their place in Chomsky's Hierarchy. It also provides a standard form for representing grammars, making it easier to compare and analyze them. Furthermore, many proof techniques in formal language theory rely on the use of CNF, making it an important concept for understanding the properties of formal languages.

Similar threads

Comp Sci Complexity for generating strings of length k from CNF grammar
    • Engineering and Comp Sci Homework Help
Replies
3
Views
976
I Proof that if T is Hermitian, eigenvectors form an orthonormal basis
    • Linear and Abstract Algebra
Replies
3
Views
2K
MHB Finishing converting to Chomsky Normal Form from a CFG?
    • Programming and Computer Science
Replies
4
Views
2K
MHB NP-complete Proof: 3-SAT is Polynomially Transformable
    • Programming and Computer Science
Replies
4
Views
2K
Computer Science theory doubts
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
A Proof of Seifert-Van Kampen Theorem
    • Topology and Analysis
Replies
2
Views
2K
I How can the maximum entropy and minimum energy principles be physical?
    • Thermodynamics
Replies
13
Views
2K
Vectors: How to prove the BAC-CAB identity w/o components?
    • Calculus and Beyond Homework Help
Replies
16
Views
4K
Proof for Closure of Vector Addition - Can You Help?
    • Special and General Relativity
Replies
2
Views
1K
A Algebraic Proofs of Levi-Civita Symbol Identities
    • Special and General Relativity
Replies
8
Views
3K

Hot Threads

Recent Insights

Back
Top