# Introduction to Theory of Computation (TOC)

**Theory of computation:** Here, we are going to learn about the **introduction of theory of computer, its definition, what is automata, its example, applications** etc.

Submitted by Mahak Jain, on November 11, 2018

**Definition:**

It is a branch of computer science that actually finds out how a problem could be solved efficiently with the help of a model of computation using some kind of an algorithm.

**What is an automata?**

It is an abstract model of digital computer. There is input tape in every automata to read input written on a file one cell at a time from left to right. Some form of output is also produced by the automation. There is also a control unit which can be in any one of the finite no of internal states.

**Examples of automata machines:**

Finite state machine, context free language, Turing machine, etc.

**Practical applications of theory of computation:**

- Traffic lights
- Lifts and elevators
- Marketing
- Compilers
- Vending machines
- Cloud computing

**Prerequisites:**

**Symbol:**a, b, c, 0, 1, 2, ...**Alphabet:**finite collection of symbols {a,b}, {0,1,2} , ...- String: sequence of symbols aaaaa,ababa,…..
**Length of string:**no. of symbols in a string |aaabc|=5**Language:**set of strings {aaaabbb,abbbc}, ...-
**Powers of 'Σ':**If Σ = {c,b} then

**Σ**= Set of all the strings over Σ of length 0. {ε}^{0}

**Σ**= Set of all the strings over Σ of length 1. {c, b}^{1}

**Σ**= Set of allthe strings over Σ of length 2. {cc, cb, bc, bb}^{2}

i.e.**|Σ**|= 4 and Similarly, |Σ^{2}^{3}| = 8 - Cardinality: it is the number of the elements in the set.
**Transition function:**An automata is supposed to operate in a discrete time frame.at one point of time, the control unit is in some internal state and the input mechanism is scanning a certain symbol on the input tape. The internal state of this control unit at the next point of time or step is called the next state or the transition function. This transition function gives the next state in terms of the current state, the current input symbol on the input tape, and the information currently in the temporary storage. During the transition from the one step to the next step, the output may get generated or the information in the temporary storage may get changed.**Move:**The term configuration refers to a particular state of the control unit, the input tape, and the temporary storage. The transition from one stage to the next is called a move.

**What is a transition graph?**

It is a directed graph. There is an initial state, internal states, and final states. the final state is also known as an accepting state. The vertices denoted by circles are used to represent states. The final state is denoted by two circles. The initial state has a one side arrow pointed towards it attached. The edges are the lines with the arrows which show the transition or the move. The edge connects one state to the other state. The edge may also be a self-loop pointing towards itself. The state is changed by using a state function and an output is given using a machine function.

**Ex:**

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions