Monday, July 22, 2019
Home > Theory Of Computation > Construct Minimal DFA That Accepts All The Strings Of 0’s & 1’s Who’s Integer Equivalent Is ≅ 3 Mod 8

Construct Minimal DFA That Accepts All The Strings Of 0’s & 1’s Who’s Integer Equivalent Is ≅ 3 Mod 8

Construct Minimal DFA That Accepts All The Strings Of 0’s & 1’s Who’s Integer Equivalent Is ≅ 3 Mod 8

Question Given Is The Binary String I Have Which I Will Convert It Into Integer And If I Divide It With ‘8’

So I Should Get Remainder ‘3’

This Is The Question Given.

 

1.Example:-

Let (11)2=(3)10

// 11 Is My Binary String Imagine, 3 Is The Decimal Equivalent Of (11)2

If I Divide (3)10 With ‘8’ I Should Get Remainder ‘3’

 

2.Example :-

(101)2=(11)10 

( String Accepted Because I’ll Get Remainder ‘3’)

First I Do Is I’ll Decide How Many Number Of States Will Come.

 

Given Is ‘ Mod 8 ‘

So All Possible Remainder Is For ‘8’

Is

I’ll Create Using Above States

Transition Table

Now I Should Decide Which One Will Be The Final State.

Given Is The Remainder Should Be ‘3’

For Remainder ‘3’ I Gave ‘q3‘ qIs Final State.

 

We Have To Find Common States And We Have To Remove Common States.

Because Question Asked Is ‘ Minimal Finite Automata ‘ So We Have To Remove Common State, So The Automata Becomes Minimal.

First Identify The Common States In The Transition Table.

-> ‘q0‘s ‘0’ Is Going To ‘q0

& ‘q4‘s ‘0’ Is Also Going To ‘q0

‘q0‘s ‘1’ Is Going To ‘q1

‘q4‘s ‘1’ Is Also Going To ‘q1

 

I Have To Remove The Common State I’m Removing ‘q4

‘q1

‘ And ‘q5‘ Are Also Common I’m Removing ‘q5

‘q2‘ And ‘q6‘ Are Also Common And Non- Final States.

q& qAre Also Common But I Can’t Merge Both.

Because

qIs Final State &

qIs Non Final State.

 

We Can’t Merge Non- Final & Final States

 

The Merged States Are Represented In Separate Table.

The Substitute  Of  ‘q4‘ Is q0‘ You Can See Before Table.

If You OBSERVE This Table Also We Have Common States In This Table Also ‘q0‘ & ‘q2

I’ll Remove(Delete) ‘q2

q& qAre Also Same But I’m Not Merging It Because One Is Final And One Is Non- Final.

I’m Drawing ‘Diagram ‘(DFA) Using Above Transition Table.

 

 

3 thoughts on “Construct Minimal DFA That Accepts All The Strings Of 0’s & 1’s Who’s Integer Equivalent Is ≅ 3 Mod 8

  1. hey there and thanks on your info – I have certainly picked up anything new from proper here. I did then again expertise several technical points the usage of this web site, as I experienced to reload the site lots of instances previous to I could get it to load correctly. I were thinking about if your hosting is OK? Not that I’m complaining, however slow loading cases instances will often impact your placement in google and can damage your quality ranking if advertising and ***********|advertising|advertising|advertising and *********** with Adwords. Well I am adding this RSS to my e-mail and can glance out for a lot extra of your respective exciting content. Ensure that you replace this once more very soon..

Leave a Reply