Theory of computation (TOC) (CS) (CS) (CS53) ( CS) Question Bank 1 (old) – View Question Bank 2 (old) – View / Download Question bank. Anna University Department of computer science engg Fifth Semester CS theory of computation (Regulation ) Semester: 5. Third Year CSE(Sem:V) 2 marks Questions and Answers NFA can be used in theory of computation because they are more flexible and easier to use than.

Author: Dikora Yozshugore
Country: Senegal
Language: English (Spanish)
Genre: Art
Published (Last): 22 April 2007
Pages: 145
PDF File Size: 1.11 Mb
ePub File Size: 3.72 Mb
ISBN: 627-2-28490-582-9
Downloads: 87125
Price: Free* [*Free Regsitration Required]
Uploader: Togami

In one move ,TM depending upon the symbol scanned by the tape head and state of the finite control:. CFL are closed under substitutionhomomorphism. Give examples of recursive languages? The Turing machine is equivalent in computing power to the digital computer.

The TM can then return to the vacated cells and answwers symbols. The recursive sets include languages accepted by at least one TM that halts on all inputs.

Decidable problems have an. Turing machine is a simple mathematical model of a computer. The languages that is accepted by TM is said to be recursively enumerable r. Consider answegs ambiguity problem for CFGs. A regular expression is a string that describes the whole set of strings according to certain syntax rules.

This problem is undecidable as there is no algorithm to solve this problem. Let P n be a ststement about a non negative integer n.


ID describe the configuration of a PDA at a given instant. Language is a set of valid strings from some alphabet. The state of the Finite control represents the state and the second element represent a symbol scanned. The left move is: What are the techniques for Turing machine construction?


State the equivalence of acceptance by final state and empty stack. When is a trivial property? Q s a finite set of states. There are no transitions from any of the halt states of any given TM. Theorh Share Share Sith Share.

The notion of computable function can be identified with the class of partial recursive functions is known as Church-hypothesis or Church-Turing thesis. A specific Universal Turing machine U is:. Depending on the state and symbol scannedthe device changes stateprints a new symbol and moves its tapehead in one of the 2k directions, either positively or negatively ,along one of the k-axes.

Thus reg exp identifies token compuattion a language. They are similar to r. The move dependent on the input symbol a bani is:.

Write examples with diagrams. Let L be any CFL. Depending on the current state and input symbol read from the input compuhation it changes state. Turing machine can change symbols on its tapewhereas the FA cannot change symbols on tape. Find CFG with no useless symbols equivalent to: Xk respectively then A X1X2….

TM has throry and unrestricted memory and is a much more accurate model of a general purpose computer.

What is a Diagonalization language Ld? What are the applications of Context free languages. These expressions are used by many text editors and utilities to search bodies of text for certain patterns etc.

Finally the productions are: Why are switching circuits called as finite state systems? What are the components of Finite automaton model? What is the crucial assumptions for encoding a TM?

  ISO 7176-14 PDF

Theory of Computation – TOC – Computer Science- Anna University – Question bank – CS

Is it true that the language accepted by a PDA by empty stack and final states are different languages. A language is regular if it is accepted by some finite automaton. So we require a PDA ,a machine that can count without limit.

A language L is recursively enumerable if there is a TM that accepts L and. L is recursively enumerable iff satisfies the following properties:. A sentence is a string of terminal symbols. The grammar has the production P as:. What are the possibilities of a TM when processing an input cs203

The most obvious way to do this is to treat the entire nonblank portion of the initial tape as inputand to treat the computahion blank portion of the tape when the machine halts as output. Finite Automata is used to model regular expression and cannot be used to represent non regular languages. Let P,Q be any two regular languages.


The tape head moves to the rightrepeatedly storing the symbols in the FC and replacing the symbols read from the cells to the left. That is a G string is in L G if:. The halting problem for TMs is: