We now have a good understanding of regular languages and the basic setup of context-free languages via context-free grammars.
But how do they relate to eachother?
We can illustrate this by illustrating how we can build up the specification for a regular language via its definition through a context-free grammar.
To express the language L = {}, we can use the following empty set of grammar rules:
ø = {}
To express the language L = {ε}, we can use the following grammar rule:
S → ε
To express the regular language L = {σ} | σ ∈ Σ, we can use the following grammar rule:
S → σ
For regular languages R1 and R2, we can construct the regular language L = R1R2 via the following grammar rule:
S → R1R2
For regular language R1 and R2, we can construct the regular language L = R1 ∪ R2 via the following grammar rules:
S → R1
S → R2
Since we have a choice of whether to product R1 or R2 above, we have implemented the union operator.
For regular language R1, we can construct the regular language L = R* via the following grammar rules:
S → R1S
S → ε
Here, we wil use the first production as many times as we have repetitions of R1, then terminate our derivation using the second production. Note that the empty string can be derived by immediately using the second production.
In general, determining whether a context-free grammar represents a regular language is a difficult problem to solve.
Here, we will look at some examples of context-free grammars that do and do not represent a regular language.
Example
Σ = {a, b, c}
S → ab
S → cb
By inspection, L = {ab, cb}. This language is finite, and hence, regular.
Example
Σ = {a, b, c}
S → AB
A → a
B → bcB
B → ε
By inspection, L = {a, abc, abcbc, ...}. It can be expressed by the following regular expression:
R = a(bc)*.
Example
Σ = {a, b}
S → abAab
A → S
A → ε
By inspection, L = {abab, abababab, abababababab, ...}. It can be expressed by the following regular expression:
R = abab(abab)*
Example
Σ = {a, b}
S → aSb
S → ε
By inspection, L = {ε, ab, aabb, aaabbb, ...}. This language is not regular.
Example
Σ = {a, b, c}
S → abCa
C → c
C → S
By inspection, L = {abca, ababcaa, abababcaaa, ...}. This language is not regular.
In conclusion, all regular languages are context-free but not all context-free languages are regular. Determining whether a context-free language is regular is not straightforward.
GitHub Repository: https://github.com/bprollinson/ripal
Copyright © 2017 Brendan Rollinson-Lorimer