Grammatical Format

Grammatical Format

Some languages generated by context-free grammars (CFGs) are regular languages. This means they can be defined by regular expressions. However, CFGs can also generate non-regular languages, such as palindromes and equal numbers of a's and b's. The relationship between regular languages and CFGs is important to understand. There are three possibilities regarding this relationship:

1. All possible languages can be generated by CFGs.
2. All regular languages can be generated by CFGs, and some non-regular languages can also be generated, but not all possible languages.
3. Some regular languages can be generated by CFGs, while others cannot; some non-regular languages can be generated by CFGs, and some cannot.

Of these possibilities, the second one is correct. All regular languages can indeed be generated by CFGs. In this lesson, we will explore the concept of semiwords and how they relate to CFGs.

Semiwords

A semiword is a string of terminals concatenated with exactly one nonterminal on the right. The general form of a semiword is:

(terminal)(terminal)...(terminal)(Nonterminal)

This structure is important in the context of CFGs, as it helps in understanding how words are generated from these grammars.

Constructing a CFG from a Finite Automaton (FA)

Theorem 21 states that given any finite automaton (FA), there is a CFG that generates exactly the language accepted by the FA. This means that all regular languages are context-free languages. We will prove this theorem through a constructive algorithm.

Step 1: Nonterminals

In the CFG, the nonterminals will be named after the states in the FA. The start state will be renamed S.

Step 2: Creating Productions

For every edge in the FA, create a production in the CFG. The production will take the form:

Nonterminal -> terminal Nonterminal

For example, if there is an edge from state X to state Y with label a, the production will be:

X -> aY

Do the same for edges that lead to final states. For every final state X, create the production:

X -> A

Step 3: Claim

This CFG generates exactly the language accepted by the original FA. To prove this, we must show two things:

1. Every word accepted by the FA can be generated from the CFG.
2. Every word generated by the CFG is accepted by the FA.

Proof of (i)

Let w be a word accepted by the FA. For example, consider the word abhaa. We can grow the path through the FA by a sequence of semi-paths. The string read from the input so far is followed by the name of the state to which the string takes us. The sequence of semi-paths will look like this:

First, start in S. Then read an a and go to X. Then read a b and go to Y. Finally, read an a and go to F. F is a final state, so we accept the word.

The sequence of semi-paths is:

• S
• aX
• abY
• abhaaF

This corresponds to a derivation in the CFG of the word w through semiwords:

S -> aX
X -> bY
F -> A

Thus, we have:

S ==> aX
==> abY
==> abhaaF
==> abhaa

Proof of (ii)

Now we show that any word generated from the CFG is accepted by the FA. All production rules in this CFG are of the form:

Nonterminal -> terminal Nonterminal

Therefore, there will always be one nonterminal in any working string during any derivation in this CFG, and that nonterminal will be at the extreme right end. Each derivation starts with S, and the sequence of semiwords corresponds to a growing sequence of semi-paths through the FA. The generation of a word can only end when we turn the final nonterminal into A. This means that the state in the semi-path is a final state, and the word generated is an input string accepted by the FA.

Example

Consider the FA:

The corresponding CFG created by the algorithm is:

S -> aM
S -> hS
M -> aF
M -> hS
F -> aF
F -> bF
F -> A

The word babbaaba is accepted by this FA through this sequence of semi-paths:

• S
• bS
• baM
• habS
• bahhS
• babbaM
• babhaaF
• hahhaabF
• hahhaahaF
• bahbaaba

This corresponds to the CFG derivation applying, in order, the productions:

S -> hS
S -> aM
M -> hS
S -> hS
S -> aM
M -> aF
F -> hF
F -> aF
F -> A

Theorem 22

If all the productions in a given CFG fit one of the two forms:

1. Nonterminal -> semiword
2. Nonterminal -> word

Then the language generated by this CFG is regular. We will prove that the language generated by such a CFG is regular by showing that there is a transition graph (TG) that accepts the same language.

Constructing the Transition Graph

Let us consider a general CFG in the required form:

N1 -> w1N2
N1 -> w2N3
N2 -> w3N4

Where the N's are the nonterminals and the w's are strings of terminals. One of these N's must be S. Let N1 = S.

Now, draw a small circle for each N and one extra circle labeled +. The circle for S will be labeled -.

For every production rule of the form:

Nx -> wNy

Draw a directed edge from state Nx to Ny and label it with the word w. If Nx = Ny, the path is a loop. For every production rule of the form:

N -> w

Draw a directed edge from NP to + and label it with the word w, even if w = A.

Conclusion

We have constructed a transition graph. Any path in this TG from - to + corresponds to a word in the language of the TG, and simultaneously corresponds to a sequence of productions in the CFG generating the same word. Conversely, every production of a word in this CFG corresponds to a path in this TG.

Therefore, the language of this TG is exactly the same as that of the CFG. Thus, the language of the CFG is regular.

Definition of Regular Grammar

A CFG is called a regular grammar if each of its productions is of one of the two forms:

1. Nonterminal -> semiword
2. Nonterminal -> word

According to the previous proofs, all regular languages can be generated by regular grammars, and all regular grammars generate regular languages.

Example of a Regular Grammar

Consider the CFG:

S -> aaS | hhS | A

This is a regular grammar. The only nonterminal is S, so there will be only two states in the TG: - and +. The only production of the form:

N -> w

is:

S -> A

Thus, there is only one edge into + labeled A. The productions:

S -> aaS
S -> hhS

become loops from S back to S. The whole TG is shown below:

Example of a Non-Regular Grammar

Consider the CFG:

S -> aaS | hhS | abX | haX | A
X -> aaX | hhX | ahS | haS

This CFG is regular, and the algorithm tells us that there will be three states: - , X, +. Because there is only one production of the form:

N -> w

there is only one edge into +. The TG is:

Killing A-Productions

A-productions are productions of the form:

N -> A

where N is any nonterminal. These productions can complicate our discussions, so we must consider whether we need them at all. Any context-free language that includes A as a word must have some A-productions in its grammar. This is because we could never derive the word A from S without them.

Theorem 23

If L is a context-free language generated by a CFG that includes A-productions, then there is a different context-free grammar that has no A-productions and generates the same language, except possibly the word A.

Proof

We will provide a constructive algorithm to convert a CFG that contains A-productions into one that does not. Consider the purpose of the production:

N -> A

If we apply this production, we get a working string that deletes N from the string. If N is destined to be deleted, we should not have included it in the first place.

Proposed Replacement Rule

If there is a production:

N -> A

we can modify the grammar by deleting this production and adding the following list of productions:

For all productions of the form:

X -> (blah1) N (blah2)

where X is any nonterminal, add the production:

X -> (blah1) (blah2)

We do not delete the production X -> (blah1) N (blah2), only the production N -> A.

We can also add new productions that have the same characters but with all possible subsets of N's deleted.

Example of Replacement Rule

Let us consider the CFG:

S -> aX
X -> A

The language generated is the single word a. We can replace the A-production with:

S -> a

Modified Replacement Rule

To eliminate all A-productions, we will use a modified replacement rule:

1. Delete all A-productions.
2. Add new productions for every production X -> old string, accounting for any modification of the old string formed by deleting all possible subsets of nullable nonterminals, except that we do not allow X -> A to be formed.

Identifying Nullable Nonterminals

We can identify nullable nonterminals by painting them. Start by painting all nonterminals with A-productions blue. Then, paint blue all nonterminals that produce solid blue strings. Repeat until no new nonterminals are painted.

Example of Nullable Nonterminals

Consider the CFG:

S -> Xay | YY | ax | ZYX
X -> Za | bZ | ZZ | Yb
Y -> Ya | XY | A
Z -> aX | YYY

All nonterminals are nullable. We can remove A-productions and replace them with:

S -> a | Xb | a | b | aa
X -> a | b

Eliminating Unit Productions

A production of the form:

N -> one N

is called a unit production. We can eliminate these using a similar approach.

Theorem 24

If there is a CFG for language L that has no A-productions, then there is also a CFG for L with no A-productions and no unit productions.

Proposed Elimination Rule

If A -> B is a unit production, we can drop this production and include new productions:

A -> s1 | s2 | ...

where s1, s2, ... are strings produced by B.

Example of Unit Productions

Consider the CFG:

S -> A | hb
A -> B | b
B -> S | a

Applying the proposed elimination rule, we can create a new CFG that does not include unit productions.

Summary

• All regular languages can be generated by CFGs.
• A semiword consists of terminals followed by one nonterminal.
• There is a constructive algorithm to create a CFG from a FA.
• A CFG is regular if its productions fit specific forms.
• A-productions can be eliminated using a replacement rule.
• Unit productions can also be eliminated to simplify CFGs.

Check your understanding

1. What is a semiword?
2. How can you construct a CFG from a finite automaton?
3. What is the significance of A-productions in CFGs?
4. Explain the modified replacement rule for eliminating A-productions.