Theory of Computation | Symbols, Alphabets, Strings and Language

Theory of computation or Automata theory mainly deals with abstract modeling of machines and computation. These models embody some of the important complex logical features we encounter, on dealing software as hardware.

The following are the basic terminologies, which are frequently used in Theory of Computation

Symbol

The smallest building entity of Automata Theory( or Theory of Computation) is known as symbol.

example: a, 2, i, B...

---

Alphabet

A set of symbols forms an alphabet.

An alphabet is usually represented by Greek letter sigma( Σ )

example: Σ= { x, y}

---

String

A string is a sequence of symbols in a alphabet.

example: 'xy' is a string derived from the alphabet Σ= { x, y}

---

Language

Collection of strings are called as a language.

example: Let an alphabet Σ= { p, q, r}

Then if a language L of set of a strings of length 2 over Σ can be represented as

L = { pp, pq, pr, qp, qq, qr, rp, rq, rr }

---

Alphabet concatenation gives you set of all strings of length of as many you do concatenation.

Let Σ = { x, y }

Σ² = Σ.Σ = { x, y }.{ x, y } = { xx, xy, yx, yy }

Star(*) operator over alphabet gives universal set of all concatenated sets.

Σ* = {ε} U Σ U Σ² U Σ³... = {ε} U { x, y } U { xx, xy, yx, yy }...

where Σ⁰ = {ε} is an empty set

---

Consider the python program.

#!/bin/python
print("helloWorld")

This piece of code get considers as combinations of strings in Theory of Computation or Automata Theory.

In order to validate, whether a certain string belongs to a language or not, we use different kinds of automata.

More over mere validation strings, automata are also used to validate a given set of language

| Previous | Types of Automata and Representation | Home |