Decision problems, Theory of Computation

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems for SL2 are decidable as well. For example, Finiteness of SL2 languages is decidable, which is to say,
there is an algorithm that, given an SL2 automaton A, returns TRUE if L(A) is finite, FALSE otherwise.

Posted Date: 3/21/2013 6:00:48 AM | Location : United States







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

Write discussion on Decision problems
Your posts are moderated
Related Questions
write short notes on decidable and solvable problem


Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1''s encountered is even or odd.

1. An integer is said to be a “continuous factored” if it can be expresses as a product of two or more continuous integers greater than 1. Example of continuous factored integers

Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had

automata of atm machine

Construct a PDA that accepts { x#y | x, y in {a, b}* such that x ? y and xi = yi for some i, 1 = i = min(|x|, |y|) }. For your PDA to work correctly it will need to be non-determin

Can v find the given number is palindrome or not using turing machine

Sketch an algorithm for the universal recognition problem for SL 2 . This takes an automaton and a string and returns TRUE if the string is accepted by the automaton, FALSE otherwi

(c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?