Formal Languages

Symbols and Alphabets

Definition: Alphabet

An alphabet is a set whose elements we call symbols.

Expressions

Definition: Expression

Let $\mathcal{A}$ be an alphabet.

An expression over $\mathcal{A}$ is a tuple of symbols from $\mathcal{A}$.

Note: Strings

Expressions are also called strings.

NOTATION

Expressions are usually written by listing their symbols directly, instead of placing them between parentheses in a comma-separated list, as is usually the case with tuples. For example, the expression $(a,2,s,s,1,w)$ is written as $a2ss1w$.

The set of all expressions which can be formed using the alphabet $\mathcal{A}$ is denoted by ${\mathcal{A}}^{\ast }$.

Definition: Concatenation

Let $\alpha$ and $\beta$ be two expressions formed from the same alphabet.

The concatenation of $\beta$ to $\alpha$ is the expression obtained by listing the symbols of $\alpha$ first and then the symbols of $\beta$.

NOTATION

$$\alpha \beta$$

Syntax

Definition: Well-Formed Formula

Let $\mathcal{L}=(\mathcal{A},\mathcal{S})$ be a formal language.

A well-formed formula in $\mathcal{L}$ is an expression in the alphabet $\mathcal{A}$ which is considered valid under the syntax $\mathcal{S}$.

NOTE

The term “well-formed formula” is often abbreviated to “wff”.

INTUITION

Well-formed formulas can be thought of as expressions which are meaningful in the context of a given language. For example, the sentence “Yesterday, Harry went to the bar” is meaningful and can be considered a wff in English. In constrast, the sentence “Fall on the in chair sock” does not carry any meaning and is, therefore, not a wff in English.

Definition: Syntax

Let $\mathcal{A}$ be an alphabet.

A syntax is a set of rules that specify which expressions in $\mathcal{A}$ are considered well-formed formulas and how to generate new wffs from existing ones.

Formal Languages

Definition: Formal Language

A formal language is an ordered pair $(\mathcal{A},\mathcal{S})$ consisting of an alphabet $\mathcal{A}$ and a syntax $\mathcal{S}$.

NOTATION

Formal languages are often denoted by $\mathcal{L}$ with or without subscripts.