How to Convert Grammar to Chomsky Normal Form?

  • Context: Undergrad 
  • Thread starter Thread starter shukur2010
  • Start date Start date
  • Tags Tags
    Form Normal
Click For Summary
SUMMARY

The discussion focuses on converting a given context-free grammar into Chomsky Normal Form (CNF). The provided grammar includes productions such as S -> bX, S -> XaX, X -> XaX, X -> XbX, and X -> a. The main challenge is addressing the production S -> bX, which does not conform to CNF. Participants emphasize the need for a systematic approach to transform the grammar while ensuring it remains free of empty strings and unit productions.

PREREQUISITES
  • Understanding of context-free grammars
  • Familiarity with Chomsky Normal Form (CNF)
  • Knowledge of grammar transformation techniques
  • Basic concepts of formal languages and automata theory
NEXT STEPS
  • Study the process of converting grammars to Chomsky Normal Form
  • Learn about the elimination of epsilon (empty string) productions
  • Research techniques for removing unit productions in grammars
  • Explore algorithms for grammar simplification and transformation
USEFUL FOR

Students and professionals in computer science, particularly those studying formal languages, automata theory, and compiler design, will benefit from this discussion.

shukur2010
Messages
1
Reaction score
0
please can i have some one know the Grammar to Chomsky Normal Form ?

and i have this exercise

S -> bX
S -> XaX
X -> XaX
X -> XbX
X -> a


please i wait your answer :(
 
Physics news on Phys.org
(This might have been answered sooner in the logic forum.)

So which productions do you want to change first? Only one is in an acceptable form. Do you have a loose algorithm? Your grammar doesn't have the empty string or any unit productions, so what's next? How do you fix S -> bX?
 

Similar threads

Graduate How to Convert Given Grammar to Chomsky Normal Form?
  • · Replies 5 ·
Replies
5
Views
25K
Undergrad Transform Grammer to Chomsky Normal Form
  • · Replies 1 ·
Replies
1
Views
6K
Graduate How can I convert this grammar into a normal form?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Proof that if T is Hermitian, eigenvectors form an orthonormal basis
  • · Replies 3 ·
Replies
3
Views
4K
Undergrad Congruence for Symmetric and non-Symmetric Matrices for Quadratic Form
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad S is set of all vectors of form (x,y,z) such that x=y or x =z. Basis?
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Differences between left vs right actions in some group theory questions
  • · Replies 1 ·
Replies
1
Views
1K
Can You Minimize Production Rules in Chomsky Normal Form?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
6K
MHB Convert the grammar into Chomsky Form
  • · Replies 29 ·
Replies
29
Views
6K