(https://bilalamjad.

net/) U a

Automata: Alphabets and Strings

by bilalamjad (https://bilalamjad.net/author/bilalamjad/) | Dec 29, 2015 | Automata
(https://bilalamjad.net/category/automata/), Computer Sciences
(https://bilalamjad.net/category/computer-sciences/) | 0 comments
(https://bilalamjad.net/automata-alphabets-and-strings/#respond)

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 2
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
2
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
2
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}

That’s all for today. If you find any problem related to this article please feel free to ask
me. Thanks for reading the article.
2
 Search

Featuring Me :)

Featured in Microsoft Friday 5 April 17

(https://blogs.msdn.microsoft.com/mvpawardprogram/2017/04/07/friday-five-april-7th/)
Featured in Microsoft Friday 5 March 17
(https://blogs.msdn.microsoft.com/mvpawardprogram/2017/03/17/friday-five-march-
17/)
Featured in Microsoft UK TechDays 17
(https://channel9.msdn.com/Events/TechDaysOnline/MVP-Led-TechDays-Online-
February-2017/Creating-a-PHP-MySQL-web-app-in-Azure-App-Service-and-deploying-
using-FTP)
Featured in Startup Weekend

Recent Posts

Short Cut Keys to Navigate between Views (https://bilalamjad.net/short-cut-keys-to-

navigate-between-views/)
Alphabetical Navigation on DOM Elements. (https://bilalamjad.net/alphabetical-
navigation-on-dom-elements/)
ForEach Vs For Loop. Which One to Use For Better Performance?
(https://bilalamjad.net/foreach-vs-for-loop-which-one-to-use-for-better-performance/)
Yes Its Hat-Trick, Microsoft Most Valuable Professional Award
(https://bilalamjad.net/bilal-microsoft-most-valuable-professional-award/)
How to calculate Hash with .NET Cryptography – Blockchain
(https://bilalamjad.net/hashing-algorithm-blockchain-azure/)
Refactoring with Visual Studio Ucalc (https://bilalamjad.net/refactoring-with-visual-
studio-ucalc/)
What’s new in C# 8 (https://bilalamjad.net/whats-new-in-c-8/)
How to fix “A potentially dangerous Request.Path value was detected from the client (&)”
(https://bilalamjad.net/how-to-fix-a-potentially-dangerous-request-path-value-was-
detected-from-the-client/)
100+ Students Trained on Machine Learning with .NET at COMSATS Lahore
(https://bilalamjad.net/100-students-trained-on-machine-learning-with-net-at-comsats-
lahore/)
2
.NET Machine Learning with 70+ Students at COMSATS Univeristy Sahiwal
(https://bilalamjad.net/net-machine-learning-with-70-students-at-comsats-univeristy-
sahiwal/)

Recent Comments
Categories

.NET (https://bilalamjad.net/category/net/) AJAX (https://bilalamjad.net/category/ajax/)

ASP.NET (https://bilalamjad.net/category/asp-net-online-sessions/)

ASP.NET (https://bilalamjad.net/category/asp-net/)

ASP.NET Online (https://bilalamjad.net/category/asp-net-online/)

Automata (https://bilalamjad.net/category/automata/)

Azure (https://bilalamjad.net/category/azure/)

Blockchain (https://bilalamjad.net/category/blockchain/)

Bootstrap (https://bilalamjad.net/category/bootstrap/) C# (https://bilalamjad.net/category/net/c/)

Community Sessions (https://bilalamjad.net/category/community-sessions/)

Computer Sciences (https://bilalamjad.net/category/computer-sciences/)

Different errors and their solutions (https://bilalamjad.net/category/different-errors-and-their-

solutions/)

exception handling (https://bilalamjad.net/category/exception-handling/)

Expression Blend (https://bilalamjad.net/category/expression-blend/)

General (https://bilalamjad.net/category/general/)

mentor ships and events (https://bilalamjad.net/category/mentor-ships-and-events/)

Microsoft (https://bilalamjad.net/category/microsoft/)

MS-SQL (https://bilalamjad.net/category/sql/)

Online Sessions (https://bilalamjad.net/category/online-sessions/)

Photoshop (https://bilalamjad.net/category/photoshop/)

PowerPoint Add-in Development (https://bilalamjad.net/category/powerpoint-add-in-development/)

SignalR (https://bilalamjad.net/category/net/signalr/)

Uncategorized (https://bilalamjad.net/category/uncategorized/)

Unity 3D (https://bilalamjad.net/category/unity-3d/)

User Interfaces (https://bilalamjad.net/category/user-interfaces/)

Visual Studio (https://bilalamjad.net/category/visual-studio/)

Web Design (https://bilalamjad.net/category/web-design/)

Windows 8 Apps (https://bilalamjad.net/category/win-8-apps/)

Windows 10 (UAP) (https://bilalamjad.net/category/windows-10-application-development/)

2
Windows Phone (https://bilalamjad.net/category/windows-phone/)

xamarin (https://bilalamjad.net/category/xamarin/) XAML (https://bilalamjad.net/category/xaml/)

Tags

.NET (https://bilalamjad.net/tag/net/) 8 (https://bilalamjad.net/tag/8/)

8.1 (https://bilalamjad.net/tag/8-1/) 2015 (https://bilalamjad.net/tag/2015/)

apps (https://bilalamjad.net/tag/apps/) ASP.NEt (https://bilalamjad.net/tag/asp-net-2/)

asp.net tutorials (https://bilalamjad.net/tag/asp-net-tutorials/)

Azure (https://bilalamjad.net/tag/azure/) background (https://bilalamjad.net/tag/background/)

bootstrap (https://bilalamjad.net/tag/bootstrap/) C# (https://bilalamjad.net/tag/c/)

center (https://bilalamjad.net/tag/center/) Choosers (https://bilalamjad.net/tag/choosers/)

Controls (https://bilalamjad.net/tag/controls/) css (https://bilalamjad.net/tag/css/)

database (https://bilalamjad.net/tag/database/)

Expression Blend (https://bilalamjad.net/tag/expression-blend/)

html (https://bilalamjad.net/tag/html/) innovation (https://bilalamjad.net/tag/innovation/)

javascript (https://bilalamjad.net/tag/javascript/) JSon (https://bilalamjad.net/tag/json/)

lahore (https://bilalamjad.net/tag/lahore/) Launchers (https://bilalamjad.net/tag/launchers/)

MIC-Lahore (https://bilalamjad.net/tag/mic-lahore/)

microsoft (https://bilalamjad.net/tag/microsoft/) MVC (https://bilalamjad.net/tag/mvc/)

mvp (https://bilalamjad.net/tag/mvp/) Pakistan (https://bilalamjad.net/tag/pakistan/)

photoshop (https://bilalamjad.net/tag/photoshop-2/) Regex (https://bilalamjad.net/tag/regex/)

Screen Scraping (https://bilalamjad.net/tag/screen-scraping/)

Silverlight (https://bilalamjad.net/tag/silverlight/) sql (https://bilalamjad.net/tag/sql/)

SQL Server (https://bilalamjad.net/tag/sql-server/) store (https://bilalamjad.net/tag/store/)

Update (https://bilalamjad.net/tag/update/) uwp (https://bilalamjad.net/tag/uwp/)

Visual Studio 13 (https://bilalamjad.net/tag/visual-studio-13/)

vs15 (https://bilalamjad.net/tag/vs15/) web scraping (https://bilalamjad.net/tag/web-scraping/)

windows (https://bilalamjad.net/tag/windows/) windows 8 (https://bilalamjad.net/tag/windows-8/)

Windows Phone (https://bilalamjad.net/tag/windows-phone/)

windows universal apps (https://bilalamjad.net/tag/windows-universal-apps/)

XAML (https://bilalamjad.net/tag/xaml/)

Archives

March 2020 (https://bilalamjad.net/2020/03/) (1)

February 2020 (https://bilalamjad.net/2020/02/) (1)
2
September 2019 (https://bilalamjad.net/2019/09/) (1)
July 2019 (https://bilalamjad.net/2019/07/) (1)
June 2019 (https://bilalamjad.net/2019/06/) (1)
March 2019 (https://bilalamjad.net/2019/03/) (5)
February 2019 (https://bilalamjad.net/2019/02/) (16)
January 2019 (https://bilalamjad.net/2019/01/) (2)
December 2018 (https://bilalamjad.net/2018/12/) (1)
November 2018 (https://bilalamjad.net/2018/11/) (1)
October 2018 (https://bilalamjad.net/2018/10/) (1)
September 2018 (https://bilalamjad.net/2018/09/) (3)
August 2018 (https://bilalamjad.net/2018/08/) (1)
July 2018 (https://bilalamjad.net/2018/07/) (2)
June 2018 (https://bilalamjad.net/2018/06/) (1)
May 2018 (https://bilalamjad.net/2018/05/) (1)
April 2018 (https://bilalamjad.net/2018/04/) (2)
March 2018 (https://bilalamjad.net/2018/03/) (2)
February 2018 (https://bilalamjad.net/2018/02/) (1)
August 2017 (https://bilalamjad.net/2017/08/) (1)
July 2017 (https://bilalamjad.net/2017/07/) (1)
June 2017 (https://bilalamjad.net/2017/06/) (1)
May 2017 (https://bilalamjad.net/2017/05/) (1)
April 2017 (https://bilalamjad.net/2017/04/) (1)
February 2017 (https://bilalamjad.net/2017/02/) (2)
January 2017 (https://bilalamjad.net/2017/01/) (1)
December 2016 (https://bilalamjad.net/2016/12/) (1)
November 2016 (https://bilalamjad.net/2016/11/) (1)
October 2016 (https://bilalamjad.net/2016/10/) (1)
August 2016 (https://bilalamjad.net/2016/08/) (1)
July 2016 (https://bilalamjad.net/2016/07/) (7)
June 2016 (https://bilalamjad.net/2016/06/) (3)
May 2016 (https://bilalamjad.net/2016/05/) (7)
April 2016 (https://bilalamjad.net/2016/04/) (2)
March 2016 (https://bilalamjad.net/2016/03/) (3)
February 2016 (https://bilalamjad.net/2016/02/) (7)
January 2016 (https://bilalamjad.net/2016/01/) (6)
December 2015 (https://bilalamjad.net/2015/12/) (7) 2
November 2015 (https://bilalamjad.net/2015/11/) (4)
October 2015 (https://bilalamjad.net/2015/10/) (5)
Recent Posts

Short Cut Keys to Navigate between Views (https://bilalamjad.net/short-cut-keys-to-

navigate-between-views/) March 14, 2020
Alphabetical Navigation on DOM Elements. (https://bilalamjad.net/alphabetical-
navigation-on-dom-elements/) February 26, 2020
ForEach Vs For Loop. Which One to Use For Better Performance?
(https://bilalamjad.net/foreach-vs-for-loop-which-one-to-use-for-better-performance/)
September 22, 2019

Latest Comments

 (https://www.facebook.com/bilal.amjad)
 (https://www.twitter.com/@mbilalamjad2) 
 (https://bilalamjad.net/feed/)
Copyrights © Bilal Amjad