display | more...

In the field of computation theory, star is one of the regular operations. If A is a language (not necessarily a regular language) then A* (read "A star") is defined as follows.

{x1x2xk | k ≥ 0 and each xi A}

In plain English: A* is the set of all strings made up of any number of consecutive strings in A, including 0.

For example, if A = {0,1},
A* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …}

Some interesting things to note about the star operation:

  • A* always contains the empty string (ε ∈ A)
  • A* is a superset, though not necessarily a proper superset, of A* (A* ⊇ A)
  • Regular languages are closed under the star operation. This means that if A is a regular language, then so is A*.

Log in or register to write something here or to contact authors.