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…