Language - Regular Language

Card Puncher Data Processing


A regular language is a language that can be described by regular expressions.

A language which cannot be described by a regular expression is called non-regular.

Context Free Grammar

Regular expressions are not very powerful at describing languages mostly due to their lack of recursion definition.

Context-free grammar(CFG) has been created to resolve this problem and defines any kind of recursive language.

A language is also regular, if its syntax can be expressed by a single context free expression. (ie they can be described by finite automata)

The requirement that a single equation suffices also implies that only terminal symbols occur in the expression. Such an expression is called a regular expression.

Programs are particularly simple and efficient:

  • for the recognition of regular sentences
  • ie for the determination of the structure of the sentence,
  • ie for the determination of whether the sentence is well-formed

Via Memory definition

If the algorithm takes:

  • a fixed, finite amount of memory, independent of the size of the input string, then the language is regular.
  • a memory amount that depends on the input string size, then the language is non-regular

1) 2)

Chapter 2 - Book - Hopcroft, Motwani, Ullman, Automata Theory, Languages, and Computation 3rd Edition. pdf

Discover More
Computer Language - (Compiler|Interpreter) - Language translator

Computer Language are written in plain text. However, computers interpret only particular sequence of instructions. This transformation from a plain text language to instructions is called compilation...
Grammar - Hierarchy of grammar (Chomsky)

In the formal languages (of computer science and linguistics), the Chomsky hierarchy is a hierarchy of formal grammars described by Noam Chomsky in 1956. The hierarchy describes the relations between:...
Lexical Analysis - (Token|Lexical unit|Lexeme|Symbol|Word)

A token is symbols of the vocabulary of the language. Each token is a single atomic unit of the language. The token syntax is typically a regular language, so a finite state automaton constructed from...
Multilingual Regular Expression Syntax (Pattern)

Regular expression are Expression that defines a pattern in text. This is therefore a language that permits to define structure of a text. They are a mathematically-defined concept, invented by Stephen...

Share this page:
Follow us:
Task Runner