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

Hhhhhhhhhhhhhhhhh, Ask question #hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh... Ask question #hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhMinimum 100 words accepted#

Sketch an algorithm to recognize the language, First model: Computer has a ... First model: Computer has a ?xed number of bits of storage. You will model this by limiting your program to a single ?xed-precision unsigned integer variable, e.g., a single one-by

Finiteness of languages is decidable, To see this, note that if there are a... To see this, note that if there are any cycles in the Myhill graph of A then L(A) will be infinite, since any such cycle can be repeated arbitrarily many times. Conversely, if the

Transition graphs, We represented SLk automata as Myhill graphs, directed g... We represented SLk automata as Myhill graphs, directed graphs in which the nodes were labeled with (k-1)-factors of alphabet symbols (along with a node labeled ‘?' and one labeled

Research poster, RESEARCH POSTER FOR MEALY MACHINE RESEARCH POSTER FOR MEALY MACHINE

Sdsdsd, dsdsd dsdsd

#titl, matlab v matlab matlab v matlab

Myhill graphs, Another way of representing a strictly 2-local automaton is ... 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

Computation of an automaton, The computation of an SL 2 automaton A = ( Σ,... The computation of an SL 2 automaton A = ( Σ, T) on a string w is the maximal sequence of IDs in which each sequential pair of IDs is related by |- A and which starts with the in

9765432165, jhfsaadsa jhfsaadsa