Question

Write a reflective journal on Grammars, Finite Automata (NFA and DFA), PDA, and Turing Machine (TM) for about one to one and half pages

Answer 1

NFA (Non-Deterministic finite automata)

• NFA stands for non-deterministic finite automata. It is easy to construct an NFA than DFA for a given regular language.
• The finite automata are called NFA when there exist many paths for specific input from the current state to the next state.
• Every NFA is not DFA, but each NFA can be translated into DFA.
• NFA is defined in the same way as DFA but with the following two exceptions, it contains multiple next states, and it contains ε transition.

In the following image, we can see that from state q0 for input a, there are two next states q1 and q2, similarly, from q0 for input b, the next states are q0 and q1. Thus it is not fixed or determined that with a particular input where to go next. Hence this FA is called non-deterministic finite automata.

Formal definition of NFA:

NFA also has five states same as DFA, but with different transition function, as shown follows:

δ: Q x ∑ →2Q

where,

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 an NFA

An NFA can be represented by digraphs called state diagram. In which:

1. The state is represented by vertices.
2. The arc labeled with an input character show the transitions.
3. The initial state is marked with an arrow.
4. The final state is denoted by the double circle.

Example 1:

1. Q = {q0, q1, q2}  
2. ∑ = {0, 1}  
3. q0 = {q0}  
4. F = {q2}  

Solution:

Transition diagram:

Transition Table:

Present State	Next state for Input 0	Next State of Input 1
→q0	q0, q1	q1
q1	q2	q0
*q2	q2	q1, q2

In the above diagram, we can see that when the current state is q0, on input 0, the next state will be q0 or q1, and on 1 input the next state will be q1. When the current state is q1, on input 0 the next state will be q2 and on 1 input, the next state will be q0. When the current state is q2, on 0 input the next state is q2, and on 1 input the next state will be q1 or q2.

Example 2:

NFA with ∑ = {0, 1} accepts all strings with 01.

Solution:

Transition Table:

Present State	Next state for Input 0	Next State of Input 1
→q0	q1	ε
q1	ε	q2
*q2	q2	q2

Example 3:

NFA with ∑ = {0, 1} and accept all string of length atleast 2.

Solution:

DFA (Deterministic finite automata)

• DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the computation. The finite automata are called deterministic finite automata if the machine is read an input string one symbol at a time.
• In DFA, there is only one path for specific input from the current state to the next state.
• DFA does not accept the null move, i.e., the DFA cannot change state without any input character.
• DFA can contain multiple final states. It is used in Lexical Analysis in Compiler.

In the following diagram, we can see that from state q0 for input a, there is only one path which is going to q1. Similarly, from q0, there is only one path for input b going to q2.

Formal Definition of DFA

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  

Transition function can be defined as:

1. δ: Q x ∑→Q  

Graphical Representation of DFA

A DFA can be represented by digraphs called state diagram. In which:

1. The state is represented by vertices.
2. The arc labeled with an input character show the transitions.
3. The initial state is marked with an arrow.
4. The final state is denoted by a double circle.

Example 1:

1. Q = {q0, q1, q2}  
2. ∑ = {0, 1}  
3. q0 = {q0}  
4. F = {q2}  

Solution:

Transition Diagram:

Transition Table:

Present State	Next state for Input 0	Next State of Input 1
→q0	q0	q1
q1	q2	q1
*q2	q2	q2

Example 2:

DFA with ∑ = {0, 1} accepts all starting with 0.

Solution:

Explanation:

• In the above diagram, we can see that on given 0 as input to DFA in state q0 the DFA changes state to q1 and always go to final state q1 on starting input 0. It can accept 00, 01, 000, 001....etc. It can't accept any string which starts with 1, because it will never go to final state on a string starting with 1.

Example 3:

DFA with ∑ = {0, 1} accepts all ending with 0.

Introduction of Pushdown Automata

We have already discussed finite automata. But finite automata can be used to accept only regular languages.
Pushdown Automata is a finite automata with extra memory called stack which helps Pushdown automata to recognize Context Free Languages.

A Pushdown Automata (PDA) can be defined as :

• Q is the set of states
• ∑is the set of input symbols
• Γ is the set of pushdown symbols (which can be pushed and popped from stack)
• q0 is the initial state
• Z is the initial pushdown symbol (which is initially present in stack)
• F is the set of final states
• δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*. In a given state, PDA will read input symbol and stack symbol (top of the stack) and move to a new state and change the symbol of stack.

  

A Turing Machine is an accepting device which accepts the languages (recursively enumerable set) generated by type 0 grammars. It was invented in 1936 by Alan Turing.

Definition

A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected.

A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q₀, B, F) where −

• Q is a finite set of states

• X is the tape alphabet

• ∑ is the input alphabet

• δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.

• q₀ is the initial state

• B is the blank symbol

• F is the set of final states

Comparison with the previous automaton

The following table shows a comparison of how a Turing machine differs from Finite Automaton and Pushdown Automaton.

Machine	Stack Data Structure	Deterministic?
Finite Automaton	N.A	Yes
Pushdown Automaton	Last In First Out(LIFO)	No
Turing Machine	Infinite tape	Yes

Example of Turing machine

Turing machine M = (Q, X, ∑, δ, q₀, B, F) with

• Q = {q₀, q₁, q₂, q_f}
• X = {a, b}
• ∑ = {1}
• q₀ = {q₀}
• B = blank symbol
• F = {q_f }

δ is given by −

Tape alphabet symbol	Present State ‘q0’	Present State ‘q1’	Present State ‘q2’
a	1Rq1	1Lq0	1Lqf
b	1Lq2	1Rq1	1Rqf

Here the transition 1Rq₁ implies that the write symbol is 1, the tape moves right, and the next state is q₁. Similarly, the transition 1Lq₂ implies that the write symbol is 1, the tape moves left, and the next state is q₂.

Time and Space Complexity of a Turing Machine

For a Turing machine, the time complexity refers to the measure of the number of times the tape moves when the machine is initialized for some input symbols and the space complexity is the number of cells of the tape written.

Time complexity all reasonable functions −

T(n) = O(n log n)

TM's space complexity −

S(n) = O(n)