CHOMSKY NORMAL FORM (CNF) & CONVERSION OF CFG TO CNF IN AUTOMATA THEORY || CFG TO CNF || TOC

CHOMSKY NORMAL FORM (CNF)
For any non-empty context-free language L, there is a grammar G, such that
L(G) = L and each rule in G is of the form
1. A → a where a ∈ Σ, or
2. A → BC where neither B nor C is the start symbol, or
3. S → where S is the start symbol
STEPS TO BE FOLLOWED IN CONVERSION OF CFG TO CNF
Step 1: Eliminate start symbol from the RHS. If the start symbol S is at the right-hand side of any production, create a new production as.
S1 → S
Step 2: In the grammar, remove the null, unit and useless productions. (Simplification of CFG)
Step 3: Eliminate terminals from the RHS of the production if they exist with other non-terminals or terminals. For example, production A → aB can be decomposed as:
A → XB
X → a
Step 4: Eliminate RHS with more than two non-terminals. For example, A → BCD can be decomposed as:
A → YD
Y → BC
---------------------------------------------------------------------------------------------------------------
AUTOMATA THEORY || THEORY OF COMPUTATION
• INTRODUCTION TO AUTOMA...
COMPILER DESIGN
• INTRODUCTION TO COMPIL...
DATABASE MANAGEMENT SYSTEM
• DATABASE MANAGEMENT SY...
DATA STRUCTURES
• INTRODUCTION TO DATA S...
JAVA PROGRAMMING
• CORE JAVA TUTORIAL FOR...
R PROGRAMMING
studio.youtube...
HTML TUTORIALS WITH IMPLEMENTATION || LEARN HTML IN 4 HOURS
• HTML TUTORIALS WITH IM...
LEARN CSS IN 3 HOURS || CASCADING STYLE SHEETS FOR BEGINNERS
• LEARN CSS IN 3 HOURS |...
JAVA SCRIPT FOR BEGINNERS IN 7 HOURS || LEARN JAVA SCRIPT IN 7 HOURS || JAVA SCRIPT
• JAVA SCRIPT FOR BEGINN...
XML (eXtensible Markup Language)
• XML (eXtensible Markup...
OPERATING SYSTEM
• OPERATING SYSTEM
ETHICAL HACKING
• Video
VI EDITOR BASICS IN LINUX / UNIX || LEARN VI EDITOR COMMANDS || LINUX || UNIX
• VI EDITOR BASICS IN LI...
HOW TO DOWNLOAD & INSTALL MySQL IN WINDOWS 10
• HOW TO DOWNLOAD & INST...
PYTHON PROGRAMS
• PYTHON PROGRAMS
C PROGRAMMING
• 01 - VARIABLES & CONST...
CORE JAVA TUTORIAL FOR BEGINNERS || LEARN CORE JAVA IN 15 HOURS || JAVA TUTORIALS FOR BEGINNERS
• CORE JAVA TUTORIAL FOR...
PYTHON TUTORIALS FOR BEGINNERS (తెలుగు లో)
• Python in One Shot(తెల...
PYTHON OOPS - MODULES - EXCEPTION HANDLING (తెలుగు లో)
• PYTHON - OOPS CONCEPTS...
PYTHON NUMPY TUTORIAL IN TELUGU (తెలుగు లో) || COMPLETE NUMPY TUTORIALS IN TELUGU
• PYTHON NUMPY TUTORIAL ...
PYTHON PANDAS TUTORIAL IN TELUGU (తెలుగు లో) || COMPLETE PANDAS TUTORIALS IN TELUGU || DATA SCIENCE
• PYTHON PANDAS TUTORIAL...
MATPLOTLIB LIBRARY - PYTHON PROGRAMMING (ENGLISH)
• MATPLOTLIB LIBRARY - P...
PYTHON DATABASE CONNECTIVITY - MYSQL & MS-EXCEL
• PYTHON DATABASE CONNEC...
DATA STRUCTURES USING PYTHON (ENGLISH)
• DATA STRUCTURES USING ...
----------------------------------------------------------------------------------------------
Instagram : / sundeepsaradhikanthety

[@anuranjnirmal]

Best explanation in youtube, understood very easily, thank you sir

[@piyalikarmakar5979]

One of the best explanation... Thanks sir🙏

[@simonneupane7680]

Thank you very much sir :))

[@abhiramthota7243]

Your videos are so good bro.... I want to talk you could you help me....

[@JD-eb5qu]

best explanation sir lot of thanks to you sir😍🤩🤩🤩🤩

[@SwetaKumari-ps2rf]

Make me to understand it easily.thnks of u sir

[@hariharasudhan.v5136]

In 17:28 it should be A-->B|S|epsilon right? because B is changed the 2nd time only

[@msking4495]

Best Explain in Hardwork

[@rajeswarirajeswari954]

Excellent explanation tq sir

[@muslimwazaef1334]

"Eliminate unit production" In step 3 you have done mistake.

[@omkaromkar5215]

How

[@masterashcoc]

Crazy explanation, thank you so much sir:)

[@kolantiramya7739]

Thank you sir🙏

[@shizuka9597]

You missed S in eliminating unit production.

[@kirankumar-tq5ce]

Best explanation sir

[@parthvaghela3306]

best Explanation ever

[@-SatyajitSahoo-]

Really helped ❤️ Thank you sir 🙏🏻......

[@me.mouni096]

Thank you sir. ❤

[@sekhar.143]

Thank you ❤sir

[@steeve9]

👌👌 explanation

[@EMG_000]

THANK YOU SIR.

[@yogeshrai3321]

Bhaiii dimaak kaa bharosaa ho gaya is conversion me🥲🥲

[@divyaagarwal3091]

Thankyou so much sir

[@pratikbhat2325]

thank u siir

[@sahithchary4392]

Super

[@user-zs8ni7yt6g]

s u did a mistake in 3rd step

[@muslimwazaef1334]

Try to correct your mistake

[@itthegamer1134]

Sir explain perfectly sir not understand

[@arzanishath8085]

S-->aS/AB/epsilon A-->epsilon B--->epsilon D--->b can anyone plz say the answer for this

[@laavanyasri4730]

Step1 - removal of useless symbols The D production is removed since it do not take place in any step of derivation of a string . S-->aS | AB | ep A-->ep B-->ep Step 2 - ep productions elimination We've A-->ep....substitute in rule S-->AB...since A is ep...we get S-->B. The obtained productions are (since A-->ep is removed) S--> aS | AB | B | ep B-->ep Now, we've B-->ep substituting the B in S rules S-->AB -->A ep -->A Obtained productions are (B-->ep is eliminated) S--> aS | AB | B | A | ep Now we've S-->ep substituting it in S-->aS we get S-->a and S-->ep is eliminated Obtained productions are S--> aS | AB | B | A | a | ep Step 3 ..elimination of unit productions We've got S-->B & S-->A unit productions. the values of A and B should be replaced with the rules ...since we don't have any rules or productions left with A and B.....the above mentioned 2 rules S-->A and S-->B can be simply eliminated... The final productions obtained are S--> aS | AB | a .

[@bece3oo3ourvishrdesai12]

​@@laavanyasri4730can you help me

[@me.mouni096]

​@@laavanyasri4730 As sir said in first step we have to right S1-->S because S is present on both RHS and LHS

[@radhikakhanna7587]

What if we remove useless production after unit production S-> aS|AB|a Here then AB would also be a useless production

[@kennadysil7806]

Thank you🙏 sir