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
Kleene called this the Synthesis theorem because his (and your) proof gives an effective procedure for synthesizing an automaton that recognizes the language denoted by any given r

Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the

Claim Under the assumptions above, if there is an algorithm for checking a problem then there is an algorithm for solving the problem. Before going on, you should think a bit about

Suppose A = (Q,Σ, T, q 0 , F) is a DFA and that Q = {q 0 , q 1 , . . . , q n-1 } includes n states. Thinking of the automaton in terms of its transition graph, a string x is recogn

Another way of representing a strictly 2-local automaton is with a Myhill graph. These are directed graphs in which the vertices are labeled with symbols from the input alphabet of

We will assume that the string has been augmented by marking the beginning and the end with the symbols ‘?' and ‘?' respectively and that these symbols do not occur in the input al

When we say "solved algorithmically" we are not asking about a speci?c programming language, in fact one of the theorems in computability is that essentially all reasonable program

Automata and Compiler (1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last f

The generalization of the interpretation of strictly local automata as generators is similar, in some respects, to the generalization of Myhill graphs. Again, the set of possible s

Differentiate between DFA and NFA. Convert the following Regular Expression into DFA. (0+1)*(01*+10*)*(0+1)*. Also write a regular grammar for this DFA.