notes, Theory of Computation

write short notes on decidable and solvable problem
Posted Date: 3/22/2013 7:33:45 AM | Location :







Related Discussions:- notes, Assignment Help, Ask Question on notes, Get Answer, Expert's Help, notes Discussions

Write discussion on notes
Your posts are moderated
Related Questions
Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici

examples of decidable problems

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

It is not hard to see that ε-transitions do not add to the accepting power of the model. The underlying idea is that whenever an ID (q, σ  v) directly computes another (p, v) via


For every regular language there is a constant n depending only on L such that, for all strings x ∈ L if |x| ≥ n then there are strings u, v and w such that 1. x = uvw, 2. |u

a) Let n be the pumping lemma constant. Then if L is regular, PL implies that s can be decomposed into xyz, |y| > 0, |xy| ≤n, such that xy i z is in L for all i ≥0. Since the le

The Emptiness Problem is the problem of deciding if a given regular language is empty (= ∅). Theorem 4 (Emptiness) The Emptiness Problem for Regular Languages is decidable. P


One might assume that non-closure under concatenation would imply non closure under both Kleene- and positive closure, since the concatenation of a language with itself is included