Recursive definition of languages in Automata

By: Prof. Dr. Fazal Rehman | Last updated: June 8, 2024

In the Theory of automata, languages can be defined with different techniques. Some of these are mentioned below;

• Language definition by using the Descriptive definition
• Language definition by using the Recursive definition
• Language definition by using the Regular Expressions (RE)
• Language definition by using the Finite Automaton(FA)

What is Recursive definition of languages?

Three steps are required in recursive definition of a language.

Step 1: Base Case: Need to define some basic words in the language.

Step 2: Recursive Step:

Defines how to build new elements of the language from already defined elements.

Step 3: Closure: The strings constructed in step 1 and step 2 are valid strings, all other string are invalid and not to be a part of language.

Example of Recursive definition of languages

Recursive definition of EVEN length strings

Step 1: 2 is in EVEN.

Step 2: If x is in EVEN, then x+2 and x-2 are EVEN. For example, if 2 is even then, 4 is also even  number.

Step 3:

The strings constructed in step 1 and step 2 are valid strings (for example 2, 4, 6, 8,….)

All other string are invalid and not to be a part of language. (for example 1, 3, 5, 7, 9,….)

Examples

1. Recursive definition of Balanced Parentheses
2. Recursive definition of Palindromes
3. Recursive definition of Strings with Equal Numbers of a’s and b’s
   Recursive definition of Language of Strings Over {0, 1} Ending in 0
4. Recursive definition of Language of Strings Over {a, b} Where Every a is Followed by b
5. Recursive definition of Language of Strings Over {a, b} Where the Number of a’s is Odd
6. Recursive definition of Language of Strings Over {0, 1} Representing Binary Numbers Divisible by 3