## Halting problem

The halting problem is a decision problem about properties of computer programs on a fixed Turing- complete model of computation, i.e. all programs that can be written in some given…

## Regular Expressions

Regular expression over ∑={a,b,c} that represent all string of length=>  (a+b+c)(a+b+c)(a+b+c)String having zero or more=> a*String having one or more=> a+All binary string.=>(0+1)*0 or more occurrence of either a or b or both=> (a+b)*1…

## Prove that L = {ww | w ∈ {0, 1}∗} is not regular

Assume that L is regular. Let p be the pumping length guaranteed by the Pumping Lemma.Take w =0p10p1 . Clearly, w ∈ L, and |w| ≥ p. We need to…

## Show that the problem of whether a Turing machine, when started on a blank tape, ever writes a given symbol (say a) of its input alphabet on its tape is not decidable

Assume the problem was decidable. Then there must be a total Turing machine Ma deciding it. We shall use Ma to build a new total Turing machine M∈ deciding the…

## Explain why the trivial properties of the recursively enumerable sets are decidable, by suggesting suitable total Turing machines for these properties

Solution: There are exactly 2 trivial properties: the empty set (of r.e. sets) and the set of all r.e. sets. Since we represent every r.e. set by some (encoding of…

## Convert from NFA to DFA using Thompson’s rule for (a+b)*abb

NFA for (a+b)*abbε – closure (0) = {0,1,2,4,7} —- Let AMove(A,a) = {3,8}ε – closure (Move(A,a)) = {1,2,3,4,6,7,8}—- Let B Move(A,b) = {5}ε – closure (Move(A,b)) = {1,2,4,5,6,7}—- Let C   Move(B,a)…

## Explain Finite automata(NFA & DFA)

We compile a regular expression into a recognizer by constructing a generalized transition diagram called a finite automataA finite Automata or finite state machine is a 5-tuple(S,∑,S0,F,δ) where S is…

## Explain Transition Diagram

A stylized flowchart is called transition diagramPositions in a transition diagram are drawn as a circle and are called statesStates are connected by arrows called edgesEdge leaving state have label…

## Reorganization of Token

Here we address how to recognize tokenWe use the language generated by following grammar,                 stmt → if expr then stmt               …

## Explain Regular Definition

A regular definition gives names to certain regular expressions and uses those names in other regular expressionsHere is a regular definition for the set of Pascal identifiers that is define…