Class 20 - Null Input/Empty Input/ε- Moves/Epsilon Moves

 Null Input/Empty Input/ε- Moves/Epsilon Moves

ε is not a member of Σ (set of Input Symbol)

ε is null input or nothing.

We can not used to calculate with string because it is nothing.

Example : 

         εa = a

         εaεε = a

         εabεεc = abc

         εεεaεb = ab    etc.

Why we use ε :

ε gives the facility of jumping of control from one state to another without scanning any input symbol, It is just a facility.

EXAMPLE 1 :

EXAMPLE 2 :

EXAMPLE 3 :

This is all about the concept of Null Input/Empty Input/ε- Moves/Epsilon Moves , I hope you understand. We will meet on next post so till radhe radhe.

Class 19 - CONSTRUCTION OF FINITE AUTOMATA (FA)

7. Constrict a DFA which accept number ( integer) divisible by 3 or (multiple of 3) .

Solution:

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string having 0 - 9  number  i.e 10 numbers because any number divisible by 3 the resulting number must be between 0 - 9.

For CONSTRUCTION OF FINITE AUTOMATA (FA) we will take different cases of input string and trace it. In this case No of group = No of state.

Let we have three groups
Group1: 0,3,6,9
Group2: 2,5,8
Group3: 1,4,7

Group1 is divisible by 3.
Group2 & Group3 is not divisible by 3.

Here we have two states such as q0 , q1, q3. where q0 is final state.


let we start

Case I: Input string = If we take Group1 such as (0,3,6,9) which is divisible by 3 initially then.

Case II: Input string = If we take Group2 and Group3 such as ( 2,5,8 / 1,4,7 ) which is divisible by 3 initially then.

Formal Definition :

Q = { q0 , q1 , q2 }

Σ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

q0 = q0   Initial state

F = { q0 }

δ = 

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

Class 18 - CONSTRUCTION OF FINITE AUTOMATA (FA)

6. Constrict a DFA which accept number ( integer) divisible by 2 or (multiple of 2) .

Solution:

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string having 0 - 9  number  i.e 10 numbers because any number divisible by 2 the resulting number must be between 0 - 9.

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

Here we have two states such as q1 , q2. where q2 is final state.

let we start

Case I: Input string = If string is even numbers such as (0,2,4,6,8) between 0 - 9.

Case II: Input string = If string is odd numbers such as (1,3,5,7,9) between 0 - 9.

Formal Definition :

Q = { q1 , q2 }

Σ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

q1 = q1   Initial state

F = { q1 }

δ = 

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

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.

CLASS 13 : CONSTRUCTION OF FINITE AUTOMATA (FA)

In this post we are going to learn how to construct finite automata (FA). CONSTRUCTION OF FINITE AUTOMATA (FA) means design a machine which can accept a variety of combination of input string i.e 0/1.

Input String such as :10,100,1100,10000,1010110 etc.

Learn More About Finite Automata (FA)

Let we understand by the help of examples:

1. Construct a DFA which accept string of 0's and 1's end with substring 00.


Solution: 

Here string end with 00 means those string whose last two bits are 00 such as 100,1000, 1100, 101100, 110100 etc.

Now For CONSTRUCTION OF FINITE AUTOMATA (FA) we design a machine that can accept the above strings such as 100,1000, 1100, 110100, 100100, etc.

Let first we take Input strings in different cases. 

CASE I: Input Sting =00

 CASE II: Input Sting =000

               

CASE III: Input Sting =1000    OR   1100    OR    111000

                 

CASE IV: Input Sting =110100 

                     

CASE V: Input Sting =100100  

                   

Now this transition graph is final which satisfy all input string ended with 00.

Formal Definition:

Q = {q0, q1, q2}

Σ = {0, 1}

q0 = q0

F = {q2}

δ ( Transition table) =

Now we get final transition table on the basis of above graph. For CONSTRUCTION OF FINITE AUTOMATA (FA) we consider different cases and in CASE V we get final graph that satisfy all type of input strings end with 00.

CLASS 12 : NDFA TO DFA CONVERSION EXAMPLE

Q = { q0, q1, q2 }

2^Q = { [φ], [q0], [q1], [q2], [q0, q1], [q0, q2], [q1, q2], [q0, q1, q2] }

Σ = { 0, 1}

q0 = q0

F = {q2}

Draw transition graph according to above transition table.

Now Discard Unreachable states from graph ( जिन   स्टेट्स तक नहीं पहुचपा रहे है उनको हटा देना )  then we get new graph:

After Discard / Reject states the graph will be: 

Here q2 state is unreachable so discard it.

Now change the levels of states in graph :

Q  = {A,B,C}

Σ  = {0,1}

q0 = A

F = {C}

Transition Table (δ) will be :

SHORT CUT METHOD :

I already explain about short cut method For Review / देखने के लिए Click on Short Cut Method

Now the Transition table will be:

CLASS 11 : NDFA TO DFA CONVERSION (Short Cut Method)

Let we discuss about Short cut method for NDFA to DFA conversion.
we consider a graph given below

Q = {[φ] , [q0], [q1], [q2], [q0, q1], [q0, q2], [q1, q2], [q0, q1, q2]}

Σ = {0, 1}

q0 = q0

F = [q0]

Now write [φ] to any other suppose E