## 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*

**.**

symbolssymbols

** Alphabets**: Alphabet is

**denoted by**

*finite, non-empty set of symbols***Σ**.

Σ = { 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_{1}= 010 , w_{2}= 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

_{3}= 010 , w

_{4}= 0111 => w

_{7}= 0100111 is concatenation of w3 .w4 .

w

_{1}w

_{2}= ε . b = b . ε = b , where w

_{1}= ε and w

_{2}= 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**

#Automata Theory #Formal Language #Kleene Closure #Kleene Plus

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

_{7}| = |ac| = 2|w

_{1}| = |ε| = 0