What is a regular language?

A regular language is any language that can be defined by a regular expression. Regular languages are closed under union, intersection, concatenation, and negation. What this means is that if there are two regular languages L1 and L2, then the resulting language L3, after the union, intersection, concatenation, or negation of L1 and L2, would also be a regular language.

What is a regular expression?

Regular expression can be the following:

  • A literal character drawn from some finite alphabet

  • An empty string

  • Concatenation of two regular expressions, R and S (RS)
    • Resulting regular expression Y accepts any strings that can be decomposed into two substrings x and y, where x is accepted by R and y is accepted by S

  • Alternation of two regular expressions, R or S (R | S)
    • Resulting regular expression Y accepts any strings if it is accepted by either R or S

  • The Kleene star, R*
    • Accepts any string that can be decomposed into a sequence of strings which are all accepted by R

  • Parenthesisation, (R)
    • Limit the scope of the concatenation, alternation, and Kleene star operations

Ryan

Ryan

Data Scientist

Leave a Reply