Theory of Computation Glossary

Glossary

Theory of Computation

ACYCLIC GRAPH

A directed graph is said to be acyclic if it contains no cycles.

ALPHABET

An alphabet is a finite nonempty set of symbols.

AMBIGUITY IN CONTEXT FREE GRAMMAR

A context free grammar G sometimes generates the same string in several different ways.This type of string will have several different derivation trees and thus have several different meaning. For prograrmning language this type of result is undesirable because a given program should have a unique interpretation. If the same string can be generated in different ways then we can say the string is derived ambiguously. A grammar is called ambiguous if a string derived ambiguously from that grammar.

AUXILIARY PUSH DOWN AUTOMATA

Auxiliary push down automata (APDA) is a push down automata which has two way input and additional general purpose storage. For a fixed amount of extra storage the deterministic and non deterministic auxiliary push down automata are equivalent in language recognizing power. The class of language accepted by auxiliary push down automata with a given space bound is equivalent to the class of languages accepted by turing machines of time complexity exponential in that space bound.

BIPARTITE GRAPH

A simple graph is said to be bipartite graph if its nodes set N is partitioned into two disjoint non-empty sets N₁ and N₂ such that every edge in the graph connects a node in N₁ and a node in N₂. Also there is no edge that connects either two nodes in N₁ or two nodes in N₂.

CANONICAL DERIVATIONS

The replacement of rightmost variable from the derivation is called rightmost derivation or canonical derivation.

CELLULAR AUTOMATA

Cellular Automata are mathematical models of decentralized spatially extended systems. They consist of a large number of relatively simple individual units or cells which are connected only locally without the existence of a central control in the system. Each unit is a simple finite automata that repeatedly updates its own state where the new unit state depends on the cell’s current state and those of its immediate neighbors. Despite the limited functionality of each individual unit and restricted intersection, the system as a whole is capable of producing intricate patterns, and even of performing complicated computations. ~

CHOMSKY NORMAL FORM

In Chomsky normal form(CNF) there are restriction on the length of right hand side and the type of symbols in right hand side of production rules.

A context free grammar G is in Chomsky normal form if every production is of the form:

A → BC
or
A → a

Where A, B and C are variables and a is teminal.

CLASS NP

The class NP (nondeterministic polynomial) can be defined as a set of decision problems that can be solved by a nondeterministic algorithm in polynomial time. NP problems are the set of problems that can be solved if we always guess correctly what computation path we should follow.

CLASS P

Problems with Boolean answer are called decision problem. The class P (polynomial) can be defined as a set of decision problems that can be solved by a deterministic algorithm in polynomial time.

COMPLETE BIPARTITE GRAPH

A graph G is said to complete bipartite graph k_p,q if its nodes are partitioned into two non-empty subsets of p and q nodes respectively.

COMPLETE GRAPH

A simple graph is said be complete graph if its each pair of distinct nodes is joined by an edge.

CONCATENATION OF STRINGS

Let a and b be strings. Then ab denotes the concatenation of a and b i.e. the string formed by making a copy of a and following it by a copy of b. More precisely if a is the string composed of n symbols a = x₁x₂…….x_n and b is another string composed of m symbols b = y₁y₂ …. .ym then the concatenation of ab is the string of length n + m = x₁x₂…….x_n   y₁y₂ …….y_m

CONNECTED GRAPH

A graph G is said to be connected if there is a path connecting every pair of nodes or vertices.

CONTEXT FREE GRAMMAR

The type 2 grammar in Chomsky hierarchy is also called context free grammar. The context free grammar defines context free language that are accepted by push down automata.

CONTEXT SENSITIVE GRAMMAR

A context-sensitive grammar or type l grammar defines the language called context sensitive languages which are accepted by linear bounded automata(LBA). In a context sensitive grammar the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal(variable) symbols. The context sensitive grammar defines the con-text sensitive languages.

CYCLIC GRAPH

A directed graph which contain one more cycle is said to be a cyclic graph.

CYK ALGORITHM

The CYK algorithm is named CYK because it was invented by John Cocke, Tadao Kasami and Daniel H. Younger. This algorithm is also known as table filling algorithm. It is used to test whether the given string is a member of context free language or not.

DEAD STATES

A dead state is non accepting state which goes to itself on every possible input symbol.

DERVIATION TREE

Derivation trees are used to show how a string can be derived from context free grammar.

DETERMINISTIC FINITE AUTOMATA (DFA)

DFA stands for deterministic finite automata. In DFA corresponding to each input symbol in the input alphabet there is one and only one move from given state to next state.

DIRECTED GRAPH

A directed graph or diagraph is a graph in which all the edges are directed.

EMPTY OR NULL STRING

The string having no symbol is called empty string or we can say empty string is the string with zero occurrences of symbols. The empty string can be denoted with ___.

EXTENDED L-SYSTEM

L-system in which productions are of the fonn
b → v
Where b is in Σ and
v is in Σ*.

are not general model of computation to provide for all algorithmic computations. In an extended L-systems productions are of the form

EXTENDED TURING MACHINES

‘
Some extensions to the basic turing machine, which increase its computing power.

FINITE AUTOMATA

The finite state automaton(automaton is singular of automata) or finite state machine is an abstract machine which has five elements or tuple (mathematical language for a list of five elements). It has a set of states and rules for moving from one state to another, depending on the input symbol applied (called transition function). It has a start state, a set of accept (final) states and an input alphabet that indicates the allowed input symbols.

GRAMMARS

A grammar defines set of rules with the help of these rules valid sentences in a language are constructed.

GRAPH

A graph is a structure consisting of vertices and edges.

GREIBACH NORMAL FORM ‘

Greibach normal form there is restriction on the position in which terminals and variables can appear on right hand side of production rules. Every production in GNF must start with a single terminal followed by variables. A given context free grammar is in Greibach normal form if all the production of the form
A → aα
Where A ε V
a ε T
α ε V* (string of variables or empty).

INTRACTABLE PROBLEM

A problem is called tractable or solvable if the space and time require for implementing the problem is reasonable. Certain computational problems are solvable in principle but the solutions require so much time or space that they cannot be used in practice. Such problems are called intractable.

LANGUAGES

A language is a set of strings of symbols from some alphabet.

LEFT RECURSION

A grammar G is said to left recursive if there is a variable A whose productions are of the from
A → Ax for any x ε (v ∪ T)*.
The variable A is said to be left recursive variable. A grammar is said to left recursive if it contains at least one left recursive variable.

LEFTMOST DERIVATION

In a derivation if at each step, production rule is applied to the leftmost variable then the derivation is said to be leftmost derivation.

LENGTH OF A STRING

The length of a string is the number of positions for symbols in the string.

LINEAR BOUNDED AUTOMATA

While the power of standard turing machine can not be extended by complicating the structure of its tape, it is possibleto limit it by restrcting the way of using the tape. The tape can be restricted by allowing the machine to use only that part of the tape occupied by the input. In this way more space is available for long input strings than for short strings generating another class
of machine called linear bounded automata (LBA).

LR(K) GRAMMARS

LR(k) grammars are the subclasses of context free grammars. These grammars play an important role in the study of programming languages and the design of compliers. The compiler of programming language ALGOL is designed by implementing LR(l) parser. In LR(k) grammar
‘L’ stands for left to right scanning of the input string and ‘R’ stands for producing right most derivation and k is the number of look ahead symbols used in the input string.

L-SYSTEMS

L-systems are essentially parallel rewriting systems developed by A. Lindenmayer to model the growth pattern of certain organisms. In each step of the derivation every symbol has to be rewritten. –

MARKOV ALGORITHM

A Markov algorithm or normal algorithm is a string rewriting system that uses grammar like rules to operate on strings of symbols.

MEALY MACHINE

In mealy machine the output depends on the state and the input at any instant of time.

MIXED DERIVATION

In a derivation, if the production rule is not applied to left most variable in each step or right most variable in each step then it is called mixed derivation.

MODIFIED POST CORRESPONDENCE PROBLEM

If the first pair in the solution is the first pair on F and S lists then the PCP is said to be modified post correspondence problem.

MOORE MACHINE

In Moore machine output depends only on the states of the machine.

MULTI HEAD TUFIING MACHINE

In the basic model of turing machine, we have a single tape which is infinite in only on’ direction and single head that can read symbols from the tape or write symbols on the tape. Here we are extended the basic turing machine by allowing multiple heads. It is also known as k-head turing machine where k (k>0) is the number of heads. We are only increasing the number of heads in this model. It has only single tape as in basic model of turing machine. Designing a turing machine for some problem with multiple heads are sometime much simpler then designing the same problem with single head turing machine.

MULTIDIMENSIONAL TURING MACHINES

In multi dimensional turing machine the tape can be viewed as extended infinitely in more than one dimension. However this extension do not increase the power of turing machine. Like basic turing machine the multi dimensional turing machine also have a finite control, tape head but the tape in this model has more than one dimension. It is also known as k-dimensional turing machine, where k is the number of dimension of the tape.

MULTIGRAPH

The term multigraph is generally understood to mean that multiple edges (and sometimes
loops) are allowed.

MULTISET

A multiset is a collection of elements in which repetition of elements is counted.

MULTISTACK MACHINES

A multi stack machines are also known as k stack machines, where k is the number of stacks. Like a PDA it takes its input from an input source rather than placing the input on tape as the turing machine does. A two stack push down automata is equivalent to the turing machine.

MULTITAPE TUFIING MACHINE

A multitape turing machine is similar to the basic model of turing model with several tapes. In multitape turing machine each tape has its own head for reading and writing symbols from tape. It is also known as k-tape turing machine where k is the number of tapes (k>0). lf the value of k is one that means it has only one tape in that case it is equivalent to the basic turing machine.

NON DETERMININISTIC FINITE AUTOMATA ( NDFA)

NDFA stands for non deterministic finite automata. In non deterministic finite automata on giving input from some state of the automata there will be more than one move or no move at
all.

NON DETERMINISTIC TUFIING MACHINES

A non deterministic turing machine has a finite control and single one way infinite tape as in basic turing machine. Both the machines are differs by there transition function.

NON-DETERMINISTIC PUSHDOWN AUTOMATA

A non deterministic push down automata(NDPDA) is one in which we have to select one move among number. This means for particular input the non deterministic pushdown automata gives two or more transitions for the next state. The non deterministic PDA accepts the input string if some set of choices leads to accept state of PDA. If the any choice do not leads to the final state then the PDA rejects the input string. The non deterministic pushdown automata’s are more powerful than deterministic pushdown automatas.

NP-COMPLETENESS

Stephen Cook introduced the concept of NP-completeness in 1971 as a step toward solving P = NP. Now there are hundreds of NP complete problems exists in several fields like propositional calculus, operation research, graph theory etc. A problem L is in NP-complete if and only if L
is NP hard and L ε NP.

NULL PRODUCTIONS

Null productions are productions of the form A → ε, where A is variable.

OFF-LINE TURING MACHINES

In off line turing machine, the input tape is read only and contains end markers on both ends. The right end of the input tape contains marker $ and left end contains marker ¢.

PALINDROME

A palindrome is a string which is the same whether it is written forward or backward.

PARTIAL DERIVATION TREE I I

A partial derivation tree is a subtree in which every leaf has label from (V ∪ T)*.

PIGEONHOLE PRINCIPLE

The pigeonhole principle states that if we distribute n objects in m boxes (pigeonholes) where m > n then a least one box must have more than one object in it.

PLANNER GRAPH

A graph G is said to be planner if it can be drawn on a plane so that the edges intersect only a the nodes

POST CORRESPONDENCE PROBLEM

Post correspondence problem (PCP) is a classic undecidable problem. Its theoretical unbounded search space makes it hard to judge whether a PCP instance has a solution and to find the solutions if they exist.

POST MARKOV THUE (PMT)

A Post Markov Thue is a production system defined with four tuples as follows:
P = (Σ, Σ*, Z, P)

Where
Σ is a finite non empty alphabet.
Σ* is set of all words in Σ.
Z is set of axioms where Z ε Σ*.
P is set of production rules defined as:
αxβ → αyβ
where x and y belongs to Σ* and
α and β are the syntactic variables belongs to Σ*.

POWER OF AN ALPHABET

If Σ is an alphabet we can express the set of all strings of a certain length from that alphabet
by using an exponential notation. We define Σ i to be the set of strings of length i, each of whose
symbols is in Σ.

POWER SET OF A SET

The power set of a set P denoted 2P is the set of all subsets of P i.e. the set { S | S is a subset of P }.

PROPOSITIONS OR STATEMENTS

A proposition or statement is a declarative sentence that is either true or false, but not both.

PSEUDO GRAPH

A graph G is said to be pseudograph if it has self loops and parallel edges. Therefore every multigraph and every simple graph is a pseudograph but converes is not true.

PUMPING LEMMA FOR CONTEXT FREE LANGUAGES

The pumping lemma for context free languages is a tool for proving that certain class of languages are not context free.The pumping lemma for context free language is bit more complex than pumping lemma for regular languages. In pumping lemma for context free languages the string is divided into five parts so that the second and forth part may be repeated together any number of times and resulting string still in the language.

PUMPING LEMMA FOR REGULAR LANGUAGES

The term pumping lemma is made up of two words one is ‘pumping’ and second is ‘lemma’. The word pumping refers to generate many input strings by pushing a symbol in an input string again and again. The word lemma refers to intermediate theorem in a proof. Pumping lemma is used to prove that given language is not regular.

PUSHDOWN AUTOMATA

Pushdown automata as an automata coupled with a stack that can be used to store string of arbitrary length. The stack can be read and modified at the top. The language accepted by PDA is called context free language.

FIECURSIVE LANGUAGE 

A language is said to be recursive or decidable if there exists a turing machine T such that
1. If string s in language i.e. s ∈ L then T accepts.
2. If string s in not in language i.e. s ∉ L then T halts but it never enters an accepting state.

RECURSIVELY ENUMERABLE LANGUAGE ‘

The language recognized by the turing machine is called the recursively enumerable language.

REGULAR EXPRESSIONS

Regular expressions are algebraic description of languages. Regular expressions are used by many text editors and utilities to search a block of text for certain patten. Like other expression such as arithmetic expressions, logical expressions etc. the regular expressions also have permitted symbols and operators. i

RELATIONS 

A relation R from P to Q is a subset of the cartesian product P x Q. If P = Q, then R is said to be a relation on P.

RESTRICTED TURING MACHINES

Restricted turing machines are those machines which are obtained by putting some type of restrictions on the basic model of turing machine.

REVERSE OF A STRING

The reverse of a string can be obtained by writing symbols in reverse order. If w is a string, then wR is the reverse of w.

REWRITING SYSTEMS

The concept of rewriting systems or production systems belongs to the class of formal systems. A rewriting system consists of an alphabet Σ and a set of production rules by which a string in Σ+ can produce another. A rewriting systems consists of following:

• A set of alphabet Σ.
• A set of axioms or initial strings over Σ denoted by Z.
• A set of production rules denoted by P. The rules in P helps to derive a set of new string from the strings produced earlier.

RIGHTMOST DERIVATION

In a derivation, if the production rule is applied to the rightmost variable in each step then it is called leftmost derivation.

SATISFIABILITY PROBLEM

The input to satisfiabilty problem is the boolean formula B.The satisfiablilty problem states that “ is there a truth assignment to the variable of B that makes B true?

SENTENTIAL FORM

If G = (V, T, P, S) is a Context free grammar then any string  β ε (V ∪ T)*.
S *⇒ β is a sentential form.
If w e L(G)
and S ⇒ β1 ⇒β2⇒…… ⇒β3 = w is derivation of string w then the string Bl, BZ, Bn
which belongs to variables and terminals is called a sentential form of the derivation.
If S *⇒L B then it is called left sentential form and
If S *⇒R B then it is called right sentential form

SET

Set is a collection of elements having a property that characterizes those elements or we can say a set is a group of objects represented as a unit.

STAY OPTION TURING MACHINE

In stay option turing machine we add another option for the head movement. The tape head in stay option turing machine can move left, right or stay in same cell after reading the input.

STRING REWRITING SYSTEM

A string rewriting system is a substitution system used to perform computation using Markov algorithm.

STRINGS 

A string can be defined as a finite sequence of symbols chosen from some alphabet.

SUBSET OF A SET 
A set P is a subset of a set Q if and only if every element of P is also an element of Q. Such a relation between sets is denoted by P ⊆ Q. If P ⊆Q and P ≠ Q we call P a proper subset of Q and write P ⊂ Q.

SUBSTITUTION RULE

A production A → αβγ can be eliminated from a grammar if we replace this production with new set of productions. We replace B with all the strings that it derives in one step. It is necessary in this case that A and B are different variables.

SUBSTRING

Let w be a string. Any string of consecutive characters from w is called as substring of w.

SUBTREE OF DERIVATION TREE

The subtree of derivation tree is a particular node of the tree together with all its descendents edges connecting them and their labels. It is similar to the derivation tree except that root may not be start variable.

TERM REWRITING SYSTEM

A collection of rewrite rules are used to transform terms (expressions) into equivalent terms according to certain reduction rules such as beta reduction and delta reduction. Term rewriting system plays important role in various areas such as implementation of functional programming languages, abstract data type specification.

THE KLEENE STAR(CLOSURE)

Let Σ be the alphabet. The Kleene star Σ* denotes the set of all strings (including the empty
string ε) over the alphabet Σ.

TRANSITION TABLE

A transition table is a conventional tabular representation of a transition function.

TREE GRAPH on TREE

A graph is a called a tree if it is connected and contain no loops.

TREES

A tree is a directed graph that has no cycle and there is one distinct node called the root node of the tree that has no predecessor. The node in the tree which do not have successor are called leaves of the tree.

TURING MACHINE

Turing machine is a powerful model proposed by Alan Turing in 1936. A turing machine can do everything that a real computer can do. However, there are some problems that can not solved bu turing machine because these problems are beyond the theoretical limits of computation.

TURING MACHINE WITH SEMI-INFINITE TAPE

In turing machine with semi-infinite tape, the tape is infinite in only one direction. The tape is infinite in right direction only.

TWO WAY INFINITE TAPE

Two way infinite tape means the tape in turing machine is infinite in both directions. In two way infinite tape, the tape has no distinguished left most square and the input can be placed somewhere on consecutive cells and rest of the tape cells contains blank symbols.

UNDECIDABLE PROBLEMS g I A

There are some problems which can be proved that there is no algorithm that always solve them no matter how much time or space is allows. These types of problems are called undecidable problems.

UNIT PRODUCTIONS

Unit productions are productions of the form A → B, where A and B are variables.

UNIVERSAL TURING MACHINES

Universal turing machine which is powerful or universal because it is capable of doing anything that any other turing machine can do.

UNREACHABLE STATE

Unreachable state means state where the machine never reaches. In other words we can say that an unreachable state in the state of the automata which are not reachable from the initial state of DFA on any input sequence.

UNRESTRICTED GRAMMAR

The type 0 grammar in Chomsky hierarchy is also called unrestricted grammar or phrase structure grammar or semi-Thue grammar. A grammar with no restriction on the production rules is called unrestricted grammar. Any number of variables and terminals can appear in any order in left hand side of production rules or right hand side of production rules. In this grammar there is only one restriction that the left hand side can not be empty.

USELESS PRODUCTIONS

Useless productions include those variables(V) and terminals(T) that do not appear in derivation of any string from start symbol.

VENN DIAGRAMS

Venn diagram are often used to represent the set operations such as union, intersection and difference.

WEIGHTED GRAPH

A graph is said to be weighted graph if some real number is assigned on every edge of a graph. ‘

YIELD OF DERIVATION TREE .

The yield of derivation tree is the concatenation of the labels of the leaves from left to right.