What is a formal language in automata theory?

Automata Theory – Formal Language

In automata theory, a formal language is a set of strings of symbols drawn from a
finite alphabet.

A formal language can be specified either by a set of rules (such as regular expressions or a
context-free grammar) that generates the language, or by a formal machine that accepts (recognizes) the language.

A formal machine takes strings of symbols as input and outputs either “yes” or “no.”

Alternatively, a language can be defined as the set of strings for which a particular
machine says “yes.”

Formal languages can be grouped into a series of successively larger classes known as
the Chomsky hierarchy.

Symbols: Any single object is called symbol, for example:- 1,0, A , a , @ , # are
symbols.

Alphabets: Alphabet is finite, non-empty set of symbols denoted by Σ.
Σ = { 0,1 } , Σ = {a,b,c} are examples of alphabet.

Strings or words over Σ: String is a finite sequence of symbols from some
alphabet.

Consider alphabet , Σ = { 0,1 } then w₁= 010 , w₂= 0111.

Length of the string: It is the number of symbols in the string.
The length of empty string is 0
i.e., |ε| = 0 ; |w| = | aaba| = 4. It does not matter if the alphabets are repeated.

Concatenation of strings: It is nothing but to join two shorter strings to make a
single larger string.
w₃= 010 , w₄= 0111 => w₇= 0100111 is concatenation of w3 .w4 .
w₁ w₂= ε . b = b . ε = b , where w₁= ε and w₂= b

Kleene Closure: The Kleene closure, ∑^* is a unary operator on a set of symbols or strings, ∑, that gives the infinite set of all possible strings of all possible lengths over ∑ including ε.

Example − If ∑ = {a, b}, ∑^* = {λ, a, b, aa, ab, ba, bb,………..}

Kleene Plus: The set ∑⁺ is the infinite set of all possible strings of all possible lengths over ∑ excluding ε.
Example − If ∑ = { a, b } , ∑⁺ = { a, b, aa, ab, ba, bb,………..}

∑⁺ = ∑^* − {ε}

Language: A language is a subset of ∑^* for some alphabet ∑. It can be finite or
infinite.
Example − If the language takes all possible strings of length 2 over ∑ = {a, b},
then L = { ab, aa, ba, bb }

Formal Language Example

Symbols: a, b, c, d, e

Alphabet: ∑ = {a, b, c}

∑^*={ε,a,b,c,ab,ba,bc,bb,bbb,aab,…}

∑⁺={a,b,c,ab,ba,bc,bb,bbb,aab,…}

Language: String of length less than 3 from ∑.

{ε,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc} -> Finite Set

|w₇| = |ac| = 2

|w₁| = |ε| = 0