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. A finite sequence of symbols over some alphabet Σ.
- 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.
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 | ϵ