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.

Content free grammars

         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 | ϵ


  1. Automata Theory and Formal Languages
  2. Kleene Closure
  3. Recursive Definition of a Language

Leave a Comment

Your email address will not be published. Required fields are marked *