Question

1) Find one real-world application of DFA and do the following: a. Describe the operations of the DFA in natural language. b. Draw graphical representation of the DFA. c. Produce the matrix version of the DFA. d. Provide 3 scenarios that DFA will reject the input. 2) For the DFA in Slide-40 of CH01 do the following: a. Write the sequence of states for the inputs: 11001100, 00010001 b. Provide one input that is accepted and another that is rejected.

Answer 1

DFA can be used in Text Parsing .

A DFA is a collection of 5-tuples same as we described in the definition of FA.

1. Q: finite set of states  
2. ∑: finite set of the input symbol  
3. q0: initial state   
4. F: final state  
5. δ: Transition function  

Graphical Representation of DFA :

A DFA is represented by digraphs called state diagram.

• The vertices represent the states.
• The arcs labeled with an input alphabet show the transitions.
• The initial state is denoted by an empty single incoming arc.
• The final state is indicated by double circles.

Example

Let a deterministic finite automaton be →

• Q = {q0, q1, q2}  
• ∑ = {0, 1}  
• q0 = {q0}  
• F = {q2}

Transition matrix:-

Its graphical representation can be :-

It wil not accept strings consisting only of zeroes,