regular language

views updated

regular language (regular set; rational language) A language recognized by a finite-state automaton. Of the language classes commonly studied, the class of regular languages is the smallest and mathematically the simplest. Its importance is shown by the existence of several alternative definitions; for some of them see regular grammar, linear grammar, regular expression, Myhill equivalence, Nerode equivalence, tree grammar.