Finite Representation of language

A finite Language can be representative by exhaustive enumeration of all the string in the languages.

This method become challenging when infinite languages are considered:

A finite representation of a language involves:

1. 1. A finite sequence of symbols over some alphabet Σ.
2. 2. Different languages should have different representations for the representation to be appropriate.

Regular expression to represent a language

Every regular expression represents a string.

Example :

0* represents strings with zero or more 0’s

(0 + 1 )* 1 (0 + 1)* represents strings with zero or more 0’s.

Regular expression and the languages they represent can be defined formally and unambiguously. Unfortunately, every language cannot be represented by a regular expression.

Content free grammars to represent language

Here a word of a language is generated by applying productions a finite number of times. Derivation of a string should start from the start symbol and the final string should consist of terminal.

If G is a grammar with start symbol S and set of terminals T, then the language G is the set.

If the production rule is applied once, then we write. α ⇒ β. When it is applied a number of times then we write α ⇒ β.

The productions in a grammar appear as given below :

S A | B

A 0A | ϵ

B 0B | 1B | ϵ