Context Free Grammar (CFG) Example

 Context-Free Grammar (CFGs) are a type of formal grammar used to describe languages in terms of production rules. CFGs are commonly used in computer science to define the syntax of programming languages, as well as in natural language processing for analyzing and generating sentences.

In this blog, we'll cover 10 basic examples of CFGs to help you better understand their structure and function.

1. Simplest CFG

The simplest CFG consists of a single production rule that generates the empty string:

S -> ε

This grammar generates only one string, which is the empty string.

2. Single-Character CFG

A CFG that generates a single character can be defined using the following production rule:

S -> a

This grammar generates only one string, which is the string "a".

3. Concatenation CFG

A CFG that generates strings by concatenating two smaller strings can be defined using the following production rule:

S -> AB

A -> a

B -> b

This grammar generates strings of the form "ab", where "a" and "b" are both single characters.

4. Alternation CFG

A CFG that generates strings by choosing between two different production rules can be defined using the following production rules:

S -> A | B

A -> a

B -> b

This grammar generates strings of the form "a" or "b", but not both.

5. Repetition CFG

A CFG that generates strings by repeating a single character can be defined using the following production rules:

S -> A

A -> aA | ε

This grammar generates strings of the form "a", "aa", "aaa", and so on.

6. Parentheses CFG

A CFG that generates strings with matching parentheses can be defined using the following production rules:

S -> (S)S | ε

This grammar generates strings with any number of matching parentheses, such as "()", "(())", and "((()))".

7. Palindrome CFG

A CFG that generates palindrome strings can be defined using the following production rules:

S -> ε | aSa | bSb

This grammar generates palindrome strings made up of the characters "a" and "b", such as "a", "aba", "abba", and so on.

8. Balanced Parentheses CFG

A CFG that generates strings with balanced parentheses can be defined using the following production rules:

S -> (S)S | ε

This grammar generates strings with any number of parentheses, as long as they are balanced, such as "()", "(())", "((()))", and so on.

9. Binary Numbers CFG

A CFG that generates binary numbers can be defined using the following production rules:

S -> 0S | 1S | ε

This grammar generates binary numbers made up of the digits "0" and "1", such as "0", "1", "10", "11", "100", and so on.

10. Arithmetic Expressions CFG

A CFG that generates arithmetic expressions can be defined using the following production rules:

S -> E

E -> E + T | E - T | T

T -> T * F | T / F | F

F -> (E) | num

This grammar generates arithmetic expressions made up of addition, subtraction, multiplication, and division, as well as parentheses and numerical values.

In conclusion, these 10 basic examples of CFGs demonstrate the flexibility and power of this formal grammar in generating a variety of different languages. By understanding the structure and function