Finite Automata | Finite State Machines | Deterministic FSM

By: Prof. Fazal Rehman Shamil | Whatsapp:+923028700085

What is Finite State Automata or finite state machine?

The finite state machine also has the following names;

  1. Finite state automata (FSA)
  2. Finite automata (FA)
  3. Finite machines
  4. Finite state machines

The finite state machine is designed for accepting and rejecting the different strings of the languages from the machine. All regular languages can be represented by the FSA.

Symboles of Finite Automata (Finite State Machine FSM)

The finite state machine has the following parts;

Start state:  Representing the start of the machine.

Final state: Representing the successful end of the machine

Dead/Dummy State: Having no meaning in the strings generation. It is only designed to full the requirements of the finite state machines that every state have one transition for each alphabet.

Transition: Representing the reading of the alphabets from the finite state machine.

Strings: Strings are characters are set of characters that can be accepted or rejected by finite state machines.

finite automata fsa symbols

Rules of Finite Automata (Finite State Machine FSM)

1. Every state has strictly one transition for each alphabet. Suppose there two alphabets in the languages L={a,b}, then each state has strictly had two transitions. One transition for alphabet a and one transition for alphabet b. Let’s have another example, Suppose there three alphabets in the languages L={a,b,c}, then each state has strictly three transitions. One transition for alphabet a, one transition for alphabet b and one transition for alphabet c.

2. If the generation of any alphabet from a transition is the cause of generating some strings that are not the part of the language, and it becomes very necessary to put that alphabet on some transition, then generates the alphabet and move the machine to the dead/dummy state. Dummy state means that machine will not generate any string.

3. Every string that is part of the language should be accepted by the FSA and every string that is not part of the language should be rejected by the FSA.

4. Every language that can be generated by a regular expression can be generated by FSA.

Examples of Finite Automata (Finite State Machine FSM)

Example 1

Language of all those strings follows the following rules;

  • can’t have odd a’s except single a
  • can have many b with even a’s or no a’s.

 

finite machines

Example 2

Language of all those strings follows the following rules;

  • can’t have odd a’s except single a
  • can have many b with even a’s or no a’s.

 

finite state machine

Example 3

Language of all those strings follows the following rules;

  • can have many b or many or no aa but all strings must ends with only ba or a.

finite automata

Example 4

Language of all those strings follows the following rules;

  • must starts with a and then can have no or many a’s or b’s and ends with only ba or a

deterministic finite automata

 

Example 5

Language of all those strings follows the following rules;

  • starts with aba and then can have no or many aa and many b and always ends with ba.

finite state automata

Example 6

Language of all those strings follows the following rules;

  • many b’s but only at the begining
  • many or no aaa or bbb and then always ends with bs.

finite state machine example

Example 7

Language of all those strings follows the following rules;

  • can have no or many aaa’s or bbb’s and always end with ba.

finite automata examples

Example 8

Language of all those strings follows the following rules;

  • always starts with aa or bb and then can have no or many aa’s or b’s and then always must end with ba.

finite automata definition

Example 9

Language of all those strings follows the following rules;

  • only two strings are accepted, 11000 or 11100 and no more string.

finite state machine python

Example 10

Language of all those strings follows the following rules;

always ends with 000 or 100 and can have no or many 11’s in the starting of the string.

FSM Automata

Example 11

non deterministic finite automata

Example 12

fsm machine

Example 13

Language of all those strings follows the following rules;

finite automata in toc

Example 14

Language of all those strings follows the following rules;

deterministic finite automata examples

Example 15

Language of all those strings follows the following rules;

finite state machine definition

Example 16

Language of all those strings follows the following rules;

fsm examples

Example 17

Language of all those strings follows the following rules;

types of finite automata

Example 18

Language of all those strings follows the following rules;

finite automata geeks

Example 19

Language of all those strings follows the following rules;

finite automata tutorials

Example 20

Language of all those strings follows the following rules;

finite automata t4tutorials

Example 21

Language of all those strings follows the following rules;

finite automata with t4tutorials

Example 22

finite automata by Cohen

Example 23

finite automata Cohen Excercise

Example 24

automata Cohen Excercise solution

Example 25

Finite Machines Cohen Excercise solution

Example 26

DFA

Example 27

Example 28

DFA Examples

Example 29

Theory of automata by Cohen finite automata examples

Example 30

Example 31

Here i am showing you a list of some more important Deterministic Finite Automata used in the theory of automata and theory of computation.

  1. DFA for Regular Expression  (a+b)* (a+b)a – Click Here
  2. DFA for Regular Expression (bb)*(aa)* – Click Here
  3. DFA for Regular Expression b+a(a+b)*+a – Click Here
  4. DFA for Regular Expression (a+b)*b+(bb)*a – Click Here
  5. DFA for Regular Expression bb+a(a+b)*+aa – Click Here
  6. DFA for Regular Expression a(a+b)*+bb(a)* – Click Here
  7. DFA for Regular Expression a(a+b)b*+bb(a)* – Click Here
  8. DFA for Regular Expression b(aa)*a+a(bb)*b – Click Here
  9. DFA for Regular Expression a+a(aa+b)*(aa)b – Click Here
  10. DFA for Regular Expression a+a(aa+b)*+(aa)b – Click Here
  11. DFA for Regular Expression (a+b)b(a+b)*+(aa)*b – Click Here
  12. FA for strings starting with a and ending with a – Click Here
  13. FA for the language of all those string starting with a – Click Here
  14. FA for the language of all those string containing aa as a substring – Click Here
  15. DFA for the language of all those strings starting and ending with same letters – Click Here
  16. DFA for the language of all those strings starting and ending with different letters – Click Here
  17. DFA for the language of all those strings having double 0 or double 1 – Click Here
  18. DFA for the language of all those strings starting and ending with b – Click Here
  19. DFA for ending with b – Click Here
  20. DFA for the string of even A’s and even b’s – Click Here
  21. DFA for the regular expression of  a(a+b)*+(bb)+a(ba)*+aba+bb*(a+b)* – Click Here
  22. RegExp and DFA for strings having triple a’s or triple b’s – Click Here

Video Lecture