Modeling Computation

13.1 Languages and Grammars

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

Chapter 13

Theory of computation

Compiler design

Automata theory

Chapter 13 Modeling Computation

13.1 Languages and Grammars

Automata theory (also known as Theory Of Computation) is a theoretical branch of Computer Science and Mathematics, which mainly deals with the logic of computation with respect to simple machines, referred to as automata. 

Automata enables scientists to understand how machines compute the functions and solve problems. The main motivation behind developing Automata Theory was to develop methods to describe and analyze the dynamic behavior of discrete systems. Automata originated from the word “Automaton” which is closely related to “Automation”.

Now, let’s understand the basic terminologies, which are important and frequently used in the Theory of Computation. 

Symbol:

A symbol (often also called a character) is the smallest building block, which can be any alphabet, letter, or picture.

​

Alphabets (Σ):

Alphabets are a set of symbols, which are always finite.

String:

A string is a finite sequence of symbols from some alphabet. A string is generally denoted as w and the length of a string is denoted as |w|.

Empty string is the string with zero occurrence of symbols,

represented as ε. Nmber of Strings (of length 2) that can

be generated over the alphabet {a, b}:

- -

a a

a b

b a

b b

​

Length of String |w| = 2

Number of Strings = 4

13.2 Finite-State Machines with Output

• Finite state machine is used to recognize patterns.
• Finite automata machine takes the string of symbol as input and changes its state accordingly. In the input, when a desired symbol is found then the transition occurs.
• While transition, the automata can either move to the next state or stay in the same state.
• FA has two states: accept state or reject state. When the input string is successfully processed and the automata reached its final state then it will accept.

Finite state machine

NDFA

NDFA refer to the Non Deterministic Finite Automata. It is used to transit the any number of states for a particular input. NDFA accepts the NULL move that means it can change state without reading the symbols.

NDFA also has five states same as DFA. But NDFA has different transition function.

Transition function of NDFA can be defined as:

δ: Q x ∑ →2^Q

Example

See an example of non deterministic finite automata:

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

DFA

DFA stands for Deterministic Finite Automata. Deterministic refers to the uniqueness of the computation. In DFA, the input character goes to one state only. DFA doesn't accept the null move that means the DFA cannot change state without any input character.

​

DFA has five tuples {Q, ∑, q0, F, δ}

Q: set of all states

∑: finite set of input symbol where δ: Q x ∑ →Q

q0: initial state

F: final state

δ: Transition function

Example

See an example of deterministic finite automata:

Regular Expressions

Construct a TM for the language L = {0ⁿ1ⁿ2ⁿ} where n≥1

The simulation for 001122 can be shown as below:

The same TM can be represented by Transition Diagram:

The following are the different types /Varients of turing machines:

• Multi-tape turing machine.
• Multi-head turing machines.
• Multi-track turing machines.
• Semi-infinite turing machines.
• Universal Turing Machine.
• Alternating Turing machine.
• Non-Deterministic Turing Machine.
• Unambiguous Turing Machine.