Class 17 - CONSTRUCTION OF FINITE AUTOMATA (FA)

5. Constrict a DFA which accept a string of a's and b's contain even number of a's followed by odd number of b's. such as (b, aab, aabbb etc.)

Solution:

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string having even number of a's and odd number of b's.

For CONSTRUCTION OF FINITE AUTOMATA (FA) we will take different cases of input string and trace it.

let we start

Case I: Input string = b / aab

Case II: Input string = b / aab /aabbb /aaaabbb 

Case III: Input string = Note there are some rejected states such as (aba / aabba / aaba etc)

Formal Definition :

Q = {q0, q1, q3, q4, q5}

Σ = {a,b}

q0 = q0

F = {q3}

δ = Transition Table

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE III we get final graph.

Class 16 - CONSTRUCTION OF FINITE AUTOMATA (FA)

4. Construct a DFA which accept a string of a's and b's start and ends with the same symbol. such as ( aba, bab, a, b etc).

Solution : 

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string must start and end with same symbol.

For CONSTRUCTION OF FINITE AUTOMATA (FA) we will take different cases of input string and trace it.

let we start

Case I: Input string = a or b 

Case II: Input string = aa or bb 

Case III: Input string = aabba /aaabbba or bbaab /bbbaaab 

Formal Definition :

Q = {q0, q1, q3, q4}

Σ = {a,b}

q0 = q0

F = {q1 , q2}

δ = Transition Table

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE III we get final graph.

CLASS 15: CONSTRUCTION OF FINITE AUTOMATA (FA)

3. Construct a DFA which accept a string of a's and b's start and end with a such as  aa, aaa, aba, abba, etc.

Solution : 

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string must start and end with a.

For CONSTRUCTION OF FINITE AUTOMATA (FA) we will take different cases of input string and trace it.

let we start

Case I: Input string = aa or aaa or aaaaa or aaaaaa etc.

Case II: Input string = aba 

Case III: Input string = ababa 

Case IV: Input string = abaa 

Case V: Input string = abaaba 

Formal Definition : 

Q = {q0, q1, q2}

Σ = {a, b}

q0 = q0

F = {q2}

δ = Transition Table

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE V we get final graph.

CLASS 14 : CONSTRUCTION OF FINITE AUTOMATA (FA)

2. Construct a DFA which accept a string of 0's and 1's contain 3 consecutive 0's. Example (000, 1000, 00001, 10001, 11000, 111000 etc.)

Solution : 

 In this question we are talking about three consecutive 0's so we will take for states such as (q0, q1, q2, q3)

Let we understand with different cases by using different input strings for CONSTRUCTION OF FINITE AUTOMATA (FA) :

Case I : Input String = 000

Case II : Input String = 1000

Case III : Input String = 101000

Case IV : Input String = 101001000

Case IV : Input String = 1010010001   OR    10100100010

Formal Definition :

Q = {q0, q1, q2, q3}

Σ = {0,1}

q0 = q0

F = {q0}

δ = Transition Table

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE V we get final graph.