Select Page
What you’ll learn: In this article you’ll learn the concept of alphabets and strings in automata and will also learn what operations can be performed on any string in automata.

## Alphabet

An alphabet is a finite set of symbols. To represent alphabet in automata we use Σ (sigma symbol).Now there is a rule for checking the validation of alphabets on the basis of which we declare a set of symbols or a symbol valid or invalid.

Rule: If we have used any alphabet then it should not be prefix in the next combination or alphabet. For instance following are some of the demonstrations where we’ll declare some sets valid and some will be declared as invalid.

• Σ = {a,b}        ✓ Valid
• Σ = {a,ba,c}   ✓ Valid
• Σ = {a,ab,c}   ☓ Invalid

## String

A string is a finite sequence of letter/alphabets e.g cat,dog,house,word etc. We can also think of a string as a word.

Language is a set of strings constructed from some alphabets e.g Urdu, English etc.

## String operations

Now lets see which operations we can perform for the manipulation of a string.

### String concatenation

As the name suggest string concatenation means to join two different strings for e.g :

W=a1,a2,a3 and V=b1,b2,b3

then WV=a1,a2,a3,b1,b2,b3

### String reverse

Simply string reverse means to reverse a string or combination of string. For example:

U=ab then U(reverse)=ba

Similarly if we have (UV) then (UV)reverse=(U)reverse * (V)reverse

### String Length

As the name suggest string length refers to the length of a string or strings in a set.

Length = |W|=n

for example:

Σ={a,b}

U=abba

then |U|=4

Example 2
Σ={a,bb}

u=abba

then |U|=3

Note: Length of Concatenation Length of first string + Length of second string …….. + length of nth string.

### Empty String

Empty string also known as null string means a string with length 0 (zero). It is denoted by λ (lemda) symbol.

For example:

|λ|=0

λw=wλ=w or

λabba=abbaλ=abba

Note: Empty Language is denoted by symbol Φ (Phi). For example Φ={ }.

But make sure Φ = { } ≠{λ} because λ is a a valid string with length 0 (zero) although its null but empty language means there is no alphabet or a string inside a set or you can consider it as Φ = { } has cardinality 0(zero) but {λ} has cardinality 1 (one).

Note: {aa,bb,λ,λ} = {aa,bb,λ} (Ignore the repetition of elements and consider the repeated element as 1 (one)).

### Substring

A substring of a string S is another string S’ that occurs “in” S. For example, “the best of” is a substring of “It was the best of times”.

### Repeat Operation

As the name suggest repeat operation refers to the repeating of a string for n times. For example:

W repeated for n times = w^n=wwww….n

make sure n is number of repetition its not a power here.

### * (Star) Operation

Star operation is used to get all the possible strings from a alphabet Σ.

For example:

Σ={a,b}

then Σ* = {λ,a,b,aa,bb,aaa,bbb,ab,ba,aab,baa……. ∞}

so Σ*= {string of length 0 (zero), string of length one (1) , string of length two (2) …. ∞}

We can make 2^n combinations for example:

suppose n=3 then Σ={a,b,c} and total combinations will be 2^3=8.

### The + Operation

The + operation returns a set of all possible strings  with length 1 or greater. It is similar to the * Star operation mentioned above with a difference that we subtract λ from the combination therefore:

Σ+=Σ*- λ

For example:

Σ={a,b}

then Σ+ = {a,b,aa,bb,aaa,bbb,ab,ba,aab,baa……. ∞}

## Revising the definition of language

So now if we revise our definition for language then Language is a set of strings or is any subset of Σ*, usually denoted by L. It may be finite or infinite.

For example if we represent an infinite language in set builder notation then:

L= {a^n b^n : n>=0}