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
The objective of the remainder of this assignment is to get you thinking about the problem of recognizing strings given various restrictions to your model of computation. We will w

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


how many pendulum swings will it take to walk across the classroom?


The key thing about the Suffx Substitution Closure property is that it does not make any explicit reference to the automaton that recognizes the language. While the argument tha

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.



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