written 2.6 years ago by | • modified 2.6 years ago |
Context-Free Grammar (CFG)
- A Context-Free Grammar (CFG) is one form of grammar that is used to generate all possible patterns of strings in a given formal language.
- In CFG at the Right Hand Side (RHS) of production, there may be any number of Terminals (a, b, c, etc.) and Non-Terminals or variables (A, B, C, S, etc.) in any combination.
- So need to normalize such grammar in some specific format.
- There should be a fixed number of terminals and non-terminals, in CFG with some conditions.
- Based on this there are two normal forms are classified as follows:
- Chomsky Normal Form (CNF)
- Greibach Normal Form (GNF)
- These normal forms have nice combinatorial structures which are useful in proving the properties of CFLs.
- Here we see Chomsky Normal Form (CNF) in detail.
Chomsky Normal Form (CNF)
- A CFG is said to be in Chomsky Normal Form (in short, CNF) if the following conditions are true.
Condition 1 - A non-terminal (variable) generating two non-terminals.
For example, A → BC
Condition 2 - A non-terminal (variable) generating a terminal.
For example, A → a
Condition 3 - Start symbol generating ε.
For example, S → ε
Condition 4 - The start variable is not present on the Right Hand Side (RHS) of any rule.
Steps for converting CFG into CNF
Step 1 - Eliminate the start symbol from RHS.
If start symbol S is at the RHS of any production in the grammar, then create a new production as: S0 → S
where S0 is the new start symbol.
Step 2 - Eliminate null, unit, and useless productions.
If CFG contains null, unit, or useless production rules, eliminate them. (CFG Simplification Stage)
Step 3 - Eliminate terminals from RHS if they exist with other terminals or non-terminals.
Example – S → aA
can be decomposed as follows:
S → RA
R → a
Finally, it is equal to S → aA only.
Step 4 − Eliminate the RHS with more than two non-terminals.
Example – S → ABS
can be decomposed as follows:
S → RS
R → AB
Finally, it is equal to S → ABS only.
This indicates, in the CNF number and nature of the symbols on the RHS are strictly fixed and restricted to a specific limit.
The Given Grammar
Let’s solve the given example of grammar
S → ASB | ε
A → aAS | a
B →SbS | A | bb
- We will convert the above grammar into the CNF.
- The rules/variables that get added at each step are shown in bold font.
Step 1 –
As start symbol S appears on the RHS rule A & B.
Hence, adding a new start variable S0, creates a new production rule S0 → S
Therefore, the grammar will become:
S0 → S
S → ASB | ε
A → aAS | a
B →SbS | A | bb
Step 2 –
As grammar contains Null production S → ε
Therefore, its removal from the grammar will produce:
S0 → S
S → ASB | AB
A → aAS | a | aA
B →SbS | A | bb | bS | Sb | b
As grammar contains Unit production B → A
Therefore, its removal from the grammar will produce:
S0 → S
S → ASB | AB
A → aAS | a | aA
B → SbS | aAS | a | aA | bb | bS | Sb | b
Also, remove the unit production S0 → S
Therefore, its removal from the grammar will produce:
S0 → ASB | AB
S → ASB | AB
A → aAS | a | aA
B → SbS | aAS | a | aA | bb | bS | Sb | b
Now, we can see that A and B each derive terminal strings, and therefore so does S0.
Thus, there are no useless symbols.
The CFG is now simplified completely and now moves towards the next step.
Step 3 –
Adding variables and productions U → a and V → b, where all strings that are not with a single terminal.
Therefore, the grammar will become:
S0 → ASB | AB
S → ASB | AB
A → UAS | a | UA
B → SVS | UAS | a | UA | VV | VS | SV | b
U → a
V → b
Finally, adding new variables P and Q and productions P → AS and Q → SV, where all strings of terminals of length 3.
Therefore, the grammar will become:
S0 → PB | AB
S → PB | AB
A → UP | a | UA
B → QS | UP | a | UA | VV | VS | SV | b
P → AS
Q → SV
U → a
V → b
So this is the required CNF for a given grammar.
Answer for Define Chomsky Normal Form