Home > Theory Of Computation > Applications Of Language And String

Applications Of Language And String

The Comparision Part, Checking And Comparing The Given String With Pre Defined String Or The Checking Part Is Called As Applications Or Language And String.

 

Language Means Collection Of Strings.

String Means Collections Of Alphabets.

 

But In Language There Are Conditions, A String Must Satisfy The Condition Of The Language, To Be In Language, Otherwise The String Will Not Be There In The Language.

Let’s Know When We Will Use Language And String In Computer Science And Engineering.

 

Sample C Program

void main()

{

int a,b,c;

}

 

This Is The Simple Basic C Language Program. This Program Is A Collection Of String( void,main,int,a,b,c)

All The Strings(keywords) We See In C Are Predefined, Those Are Fixed.

 

There Are Strings Which Are Used In C Language Are Predefined, If I Give Any Other String Which Is Not Accepted By The C Program, I’ll Get A Error Message.

Example C Language

L={void,main,int,a,b,c,1,2,3…} // Predefined

 

The Comparision Part, Checking And Comparing The Given String With Pre Defined String Or The Checking Part Is Called As Applications Or Language And String.

Checking The String Wheather It Is Valid String Or Not, This Comparision Is Called Applications Or Language And String.

 

Collection Of Strings Form A Language. Like I Said, C Language Is Formed With Different Strings Like Void,Main,Int,a,b,c,1,2,3,printf,scanf,…etc

 

If You Enter Any Other Other Strings Which Doesn’t Satisfy The C Language(L={void, main, int, a,b,c,1,2,3…} )PredEfined Functions, It Shows Error.

 

There Are Two Types Of Languages.

Example

Σ = {a,b} //Input String

L1={Set Of All The Strings Having Length 2}

 

Possible Strings-

L1={aa,ab,ba,bb} // These Are The Possible Strings Generated.

This Set Is Called As Finite Set And This Language Is Called Finite Language.

Let’s Imagine That You Gave Input String To The Computer ‘ab’

And You Want To Check Whether L1

Satisfies This String Or Not.

 

What Computer Do Is, ‘ ab ‘ is compared with Each And Every string aa,ab,ba,bb Of LLanguage.

If The String Is There In The Language, The Computer Say’s Yes’ Your String Is There In The Language, Your String Satisfies The Language.

L2= { Set Of All The String Which Starts With a } Where = {a,b} Are The Input Strings.

 

The Possible Strings In The Language Is

L2={a,ab,aba,abb,abbab,abbababab……}

I Can Create Infinite Strings Which Starts With a, This Language Is Called As Infinite Language Because Infinite Strings Are Generating.

 

Now

 

I Have A String ‘ abbabbab ‘

I Want To Know Whether This String Is Present In The Language Are Not.

By Seeing Only We Can Say That This String Will Be There In The Above Set Of Language Because It Starts With a.

 

But We Human Can Directly Say By Seeing The First character a in abbabbab String, This String Will Be There But Computer Doesn’t Know Until It Checks With Each And Every String In The Language L2={a,ab,aab,aaba,aabababaaa…}

Computer Compares The String With Each And Every String To Know Whether This Is Present In The Language Or Not.

L2={a,ab,aab,aaba,aabababaaa…} Will Be There In The Main Memory Of The Computer.

With The Main Memory, I’ll Compare My String abbabbab.

It Is Not Possible To Store Whole The Set Of Language In Main Memory.

Because This Set Of Language L2={a,ab,aab,aaba,aabababaaa…}  Is A Infinite Set And I Can Generate Infinite Strings.

And My Comparision Operation Becomes Costly.

 

So, I Need A FINITE REPRESENTATION With Which I Can Judge That The Given String Is Present In The Computer Language Set Of Strings Are Not.

 

Means I Need A Language From The Computer And Enquired String. See The Below Diagram,

I Have To Check Wheather S In Present In Language Are Not, String Is Present In Language Or Not.

What I’ll Do Is I’ll Do F (FINITE REPRESENTATION).

If I Give String(S) AS Input To FINITE REPRESENTATION(F), I Should Get In Output That String Is Present Or Not In The Language.

 

What Happens Is String(S) & Language Is Given As Input To The Finite Representation (F), And Finite Machine Gives Me Output Like ‘ Yes’ Or ‘No’.

Yes- String Present

No- String Not Present

 

I Should Follow This Structure In Theory Of Computation Syllabus.

What We Have To Do Is, Give String(S) Input And Language(L) Input To The Finite State Machine(F).

We Are Going To Learn It In Detail.

 

Finite Automata Is The First Machine In The Finite State Machine.

Let’s Understand How The Finite Automata( Machine ) Is Designed As Per A Particular Language.

 

 

Example –

I’m Taking A Language,L1={Set Of All The String Start With b}

Σ = {a,b} //Input Symbol

 

I Have To Convert It Into Finite Automata.

 

This Is The Finite Automata(Machine).

I Have String baba.

 

Now

I Want To Know That This String Is Present In The Given Language Or Not.

 

L1={Set Of All String Start With b}

Means

L1={b,ba,baba,bba,babaa…} // Infinite Language And Infinite Strings

 

This Is A Infinite Language, So What I Should Do Is, It Is Important For Me To Represent It In Finite. ( Finite Representation ) We Call It.

 

So That I’ll Know The Machine Is Working Or Not.

 

See The Below Picture.

q1= Initial State (Reading Point Or Starting Point)

baba  Is The String I Want To Check, q1

Is The Initial Start Which Reads Character “One By One”(b,a,b,a).

And let’s Understand How Machine Is Moving.

 

 

First Character From baba is b

My Pointer is on q1

q

Reads b ( which is on the arrow, we call it as input symbol)

My Machine Is On qState

When I’m Reading b

My Machine Is Going To qState

 

Means On q1

It Read b

 

And Came To q

 

Now

My Machine Is On qState

 

Now Machine Pointer Is On q2

 

Now It Check’s a ( next character of b’a’ba string )

 

 

On q2

If You Are Giving a as input, Then Where It Should Go ???

You Can See , If You Are Giving Input a to q2

It(Pointer) Comes To qOnly

Machine Is Not Transitting Or Machine Is Not Moving.

Pointer Was On q

And Pointer Will Be On qOnly

 

Then b,

 

Again The Pointer Will Be On q2

For b Also Pointer Will Be On q2

 

Then a

 

If I Get a On q2

The Pointer Comes To qAgain

 

At The End Of The String baba

My Movement Is On q2

My Machine Is On q2

qIs My Final State

How I Came To Know That q

Is My Final State Because Of The DOUBLE CIRCLES To q2

Meaning For DOUBLE CIRCLES Is Final State.

 

If I Give Arrow In The First For A State (q1) , That Is Called As Starting State.

If I Give Double Circle To A State, That State Is Called Final State.

Final State Is Also Called As End State Or Acceptance State.

 

At The End Of The String (baba) If The Machine Pointer Is On Final Or Acceptance State, So It Is Confirm That The String(baba) Is Satisfying The Language L1

 

That’s Why baba String Lies On qState In L={b,ba,baba,bba,babaa…} Language.

 

We Already Know That By Seeing baba, The First Character Of This String Is Starting With b, Which Means This String Will Be Present In The Given Language.

In Output With The Machine, We Also Got That The String baba Lies On q

State In The Language L1={b,ba,baba,bba,babaa…}

 

If The Machine Stay’s On The Final State, It Is Confirm That The String Is Accepted.

 

 

Example 2 ( Rejected String)

Σ = {a,b} //Input Symbol
L1={Set Of All The String  Starts With b}

String Is aba

 

aba Is A String, Let’s See Weather It Satisfies The Language Or Not.

 

q1,q2,q3

Are Called As ‘ States ‘

Arrow For The Starting State Represents Starting State. Double Circle Represents End State Or Final State Or Acceptance State.

Arrows Between States Are Called Transitions.

The Symbols Given Above The Transitions Are Called Input Character.

 

aba is String

Machine Is Reading a At The Starting State q1 // First Character

The Pointer Came To qState

Meaning For qd

Is Death State.

 

We All Know That Anything Which Dies Will Not Come Back.

Like That

If My Machine Enter To qd

State, The Machine Pointer Will Not Come Back.

It Will Not Come Acceptance State Again If It Goes To qd

 

Machine Read The First Charecter a among aba

It Reached To Death State qd

After Reaching q

The Pointer Again Read b ( next character)

 

From q

If We Are Giving Input b

It Again Reaching To qd((Death State) Only.

Again Machine Read The a ( Next Character)

Again The Pointer Reached To qd(Death State) Only

 

My String Is Completed.

My Machine Is On Death State Only.

It Has Not Reached Final State. If My Machine Is Reaching To Death State At The End Of The String Means String(aba) Is Invalid For The L1={Set Of All The String  Starts With b} Language.

Means This String Will Not Satisfy This Language.

 

This Is How We Give Finite Automata.

 

I Didn’t Compared Given String Will Any Other String In This Task.

 

I Gave String baba And String aba To The Machine  And Machine Shown Me That Whether The String Is Valid Or Invalid.

 

If The Machine Reaches To Final State, The String Is Valid.

If The Machine Reaches To Death State Or Other Than Final State, The String Is Invalid.

We Have To Understand How We Have Drawn This Automata Diagram. This Machine Diagram.

 

In Theory Of Computation, We Will Understand How These Kind Of Machines Are Made.

 

These Are Examples For Which Explained About Machine Accepting And Rejecting The Strings.

Leave a Reply