# Recursive definition of languages in Automata

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

- Recursive definition of Balanced Parentheses
- Recursive definition of Palindromes
- 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 - Recursive definition of Language of Strings Over {a, b} Where Every a is Followed by b
- Recursive definition of Language of Strings Over {a, b} Where the Number of a’s is Odd
- Recursive definition of Language of Strings Over {0, 1} Representing Binary Numbers Divisible by 3