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

Computer architecture, What are the issues in computer design? What are the issues in computer design?

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

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

A composable-reset DFA (CR-DFA) is a five-tuple, Question 2 (10 pt): In thi... Question 2 (10 pt): In this question we look at an extension to DFAs. A composable-reset DFA (CR-DFA) is a five-tuple, (Q,S,d,q0,F) where: – Q is the set of states, – S is the alph

Algorithm for the universal recognition problem, Sketch an algorithm for th... 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

#title., distinguish between histogram and historigram distinguish between histogram and historigram

Computer architecture, What are the issues in computer design? What are the issues in computer design?

Strictly 2-local languages, The fundamental idea of strictly local language... The fundamental idea of strictly local languages is that they are speci?ed solely in terms of the blocks of consecutive symbols that occur in a word. We'll start by considering lan

Shell script, shell script to print table in given range shell script to print table in given range

Turing, turing machine for prime numbers turing machine for prime numbers