- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

CFG stands for context free grammar and CNF stands for Chomsky’s Normal Form in the theory of computation.

A context free grammar (CFG) is a forma grammar which is used to generate all possible patterns of strings in a given formal language.

It is defined as four tuples −

G=(V,T,P,S)

Where,

- G is a grammar, which consists of a set of production rules. It is used to generate the strings of a language.
- T is the final set of terminal symbols. It is denoted by lower case letters.
- V is the final set of non-terminal symbols. It is denoted by capital letters
- P is a set of production rules, which is used for replacing non-terminal symbols (on the left side of production) in a string with other terminals (on the right side of production).

A context free grammar is in CNF, if the production rules satisfy one of the following conditions

- If there is start Symbol generating ε. Example − A-> ε
- If a non-terminal generates two non-terminals. Example − S->AB
- If a non-terminal generates a terminal. Example − S->a

Follow the steps given below to successfully convert the CFG to CNF: −

**Step 1 **− Eliminate start symbol from right hand side (RHS)

If the start symbol S is at the right-hand side of any production,

Create a production as follows −

S1->S

Where, S1 is the new start symbol

**Step 2 **− In the grammar try to remove the null, unit and useless productions.

**Step 3** − Eliminate terminals from RHS of the production if they exist with other non terminals or terminals.

Example − S->aA can be decomposed as follows −

S->RA

R->a

Finally, it is nothing but S->aA only.

**Step 4** − Eliminate the RHS with more than two non-terminals.

Example − S->ABS can be decomposed as given below −

S->RS

R->AB

- Related Questions & Answers
- Design an unambiguous CFG in CNF that generates E?
- How to convert CFG to Greibach Normal Form?
- Convert the given Context free grammar to CNF
- Explain the elimination of epsilon productions in CFG
- Explain if the CFG is recognized by Non-deterministic push down automata
- Explain with an example how to convert NFA to DFA.
- Explain Arden’s theorem to convert DFA to Regular Expression
- Convert NFA to DFA and explain the difference between them
- Construct a pair of languages by using CFG
- Generate a CNF for a given context free grammar
- Eliminate epsilon, unit and useless symbols and rewrite into CNF
- How to Convert Binary to Decimal?
- How to Convert Decimal to Binary?
- How to Convert Decimal to Octal?
- How to Convert Binary to Octal?

Advertisements