Course contentsShow
← Computer Science
Lesson 1766 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Regular Expression Syntax and Basic Operators

Learn the fundamental symbols and operations in regular expressions: concatenation, union (|), and Kleene star (*).

Regular Expression Syntax and Basic Operators

What You'll Learn

You'll learn how to write regular expressions using the three fundamental operators: concatenation, union (|), and Kleene star (*).

The Core Idea

Regular expressions are a notation system for describing languages (sets of strings) over an alphabet. Think of them as a compact recipe for building strings that belong to a language.

The three basic operators work like this:

Concatenation

Write symbols side-by-side to join strings. The regular expression ab means "the string a followed immediately by b." It describes the language containing exactly one string: {ab}.

Union (|)

The vertical bar | means "or." The regular expression a|b describes the language containing two strings: {a, b}. Either one is valid.

Kleene Star (*)

The asterisk * after a symbol or expression means "zero or more repetitions." The regular expression a* describes the infinite language {ε, a, aa, aaa, aaaa, ...}, where ε is the empty string.

Combining Operators

These operators compose naturally:

  • ab|c means "ab or c" → language {ab, c}
  • (a|b)* means "zero or more of either a or b" → language {ε, a, b, aa, ab, ba, bb, aaa, ...}
  • a*b* means "zero or more a's followed by zero or more b's" → language {ε, a, b, aa, ab, bb, aaa, aab, abb, bbb, ...}

Parentheses group sub-expressions, just like in arithmetic.

Key Takeaway: Regular expressions use concatenation (adjacency), union (|), and Kleene star (*) to compactly describe languages as sets of strings over an alphabet.