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

Ask an Expert

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

Write your message here..

Related Questions

Llll, mmmm mmmm

Union, Intuitively, closure of SL 2 under intersection is reasonably easy ... Intuitively, closure of SL 2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a

Algorithm, What is the Best way to write algorithm and construct flow chart... What is the Best way to write algorithm and construct flow chart? What is Computer? How to construct web page and Designe it?

Possibility of recognizing the palindrome language, Computer has a single F... Computer has a single FIFO queue of ?xed precision unsigned integers with the length of the queue unbounded. You can use access methods similar to those in the third model. In this

What is theory of computtion, what is theory of computtion what is theory of computtion

Overview of dfa, Explain Theory of Computation ,Overview of DFA,NFA, CFG, P... Explain Theory of Computation ,Overview of DFA,NFA, CFG, PDA, Turing Machine, Regular Language, Context Free Language, Pumping Lemma, Context Sensitive Language, Chomsky Normal For

Strictly local languages, We have now de?ned classes of k-local languages f... We have now de?ned classes of k-local languages for all k ≥ 2. Together, these classes form the Strictly Local Languages in general. De?nition (Strictly Local Languages) A langu

Equivalence problem, The Equivalence Problem is the question of whether two... The Equivalence Problem is the question of whether two languages are equal (in the sense of being the same set of strings). An instance is a pair of ?nite speci?cations of regular

Sdsdsd, dsdsd dsdsd

Pumping lemma constant, a) Let n be the pumping lemma constant. Then if L i... 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