Describe the function of AX, CX and IP register of 8086 microprocessor .
AX: This is accumulator register. It gets used in arithmetic, logic and data transfer instructions. In manipulation and division, one o...
Showing posts with label Theory of Computation. Show all posts
Showing posts with label Theory of Computation. Show all posts
Convert the following regular expressions to NFA’s with ϵ-transitions. (i) 〖01〗^*; (ii) (0+1) 01; (iii) 00〖(0+1)〗^*
(i) (0 1) * (ii) (0+1) 01 (iii) 00(0+1) *
State the decidability of CFG.
Statement: Every CFG is deciable, Let A be a CFL then we know that their must be CFG G a such that L (G) = A, Now we construct a decide...
Differentiate between recursive and recursively enumerable languages.
Recursive Language: Let L be a language over an input and if TM ‘T’ (Turing machine T) excepts every word in L and rejects every wor...
What do you mean by parsing? What are the applications of parse tree?
Parsing: The CFG is an essential concept for the implementation of compilers and other programming language process. Tools such as YA...
“Every language accepted by a multi tape Turing Machine is recursively enumerable” – Explain.
Proof: Suppose language L is accepted by a k-tape TM M. We simulate M with a one-tape TM N whose tape we think of as having 2k tracks...
Explain Turing Machine Model.
A Turing machine consists of a finite control which can be in any of finite set of states. There is a tape divided into squares or cells...
Design a pushdown automaton which accepts a string of alphabet parenthesis.
Matching parenthesis using the stack: · An automaton can use the stack to recognize balanced parenthesis · e.g. (()) () ...
Describe instantaneous description of a pushdown automaton.
Figure: ID’s of the PDA of example on input 1111.
Consider the following grammar: S → ASB | ϵ A → aAS | a B → SbS | A | bb (i) Eliminate ϵ-productions; (ii) Eliminate any unit productions in the resulting grammar; (iii) Eliminate any useless symbols in the resulting grammar; (iv) Put the resulting grammar into Chomsky Normal Form (CNF)?
(i) Only S is null able, so we must chose, at each point where S occurs in a body, to eliminate it or not. Since there is no b...
Explain different ways of accepting language of pushdown automaton.
There are two different ways of accepting language of pushdown automaton. (i) Final state Acceptability (ii) Empty stack Accept...
Write a regular expression for the set of string that consists of alternating 0’s and 1’s.
A regular expression for the set of string that consists of altering 0’s and 1’s. For this we have to consider some steps, they are: St...
Define a context-free-grammar that has only strings in L (G) are a^n b^n for n ≥ 1.
Define a context-free-grammar that has only strings in L (G) are a n b n for n ≥ 1. We can represent a CFG (G) by its four compone...
Consider the grammar: S → AB | C A → aAb | ab B → cBd | cd C → aCd | aDd D → bDc | bc Show in particular that the string aa bb cc dd: (i) Parse tree; (ii) Leftmost derivation; (iii) Right most derivation; (iv) Is the grammar is ambiguous or not?
The string aa bb cc dd has two left most derivation and the two parse left most derivation and the two parse tree: (i&ii) S ...
Prove that the states are equivalent if two states are not distinguished by the table filling algorithm.
Prove that the states are equivalent if two states are not distinguished by the table filling algorithm. Proof: Let us again assume we ...
Define homomorphism with an example. Prove that h(L) is regular, if L is a regular language over alphabet Σ and h is a homomorphism on Σ.
Homomorphism: A string homomorphism is a function on string that works by substituting a particular string for each symbol, such that h...
Subscribe to:
Posts
(
Atom
)
