## 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…

## Regular expression for language It should contain at least 3 one

Regular expression for language it should contain at least 3 one. => (0+1)*1(0+1)*1(0+1)*1(0+1)*

## Regular expression for any number of a followed by any number of b followed by any number of c

Regular expression for any number of a followed by any number of b followed by any number of c => a*b*c*

## Regular expression for ∑={a,b} such that 3rd character from right end of the string is always a

Regular expression for ∑={a,b} such that 3rd character from right end of the string is always a =>  (a+b)*a(a+b)(a+b)