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

Design and implementation of the state machine, You are required to design ... You are required to design a system that controls the speed of a fan's rotation. The speed at which the fan rotates is determined by the ambient temperature, i.e. as the temperatur

Equivalence of nfas and dfas, In general non-determinism, by introducing a ... In general non-determinism, by introducing a degree of parallelism, may increase the accepting power of a model of computation. But if we subject NFAs to the same sort of analysis

Reducibility among problems, A common approach in solving problems is to tr... A common approach in solving problems is to transform them to different problems, solve the new ones, and derive the solutions for the original problems from those for the new ones

Convert chomsky normal form into binary form, Suppose G = (N, Σ, P, S) is a... Suppose G = (N, Σ, P, S) is a reduced grammar (we can certainly reduce G if we haven't already). Our algorithm is as follows: 1. Define maxrhs(G) to be the maximum length of the

Gephi, construct a social network from the real-world data, perform some si... construct a social network from the real-world data, perform some simple network analyses using Gephi, and interpret the results.

Myhill-nerode theorem, This close relationship between the SL2 languages an... This close relationship between the SL2 languages and the recognizable languages lets us use some of what we know about SL 2 to discover properties of the recognizable languages.

Class of recognizable languages, Proof (sketch): Suppose L 1 and L 2 are ... Proof (sketch): Suppose L 1 and L 2 are recognizable. Then there are DFAs A 1 = (Q,Σ, T 1 , q 0 , F 1 ) and A 2 = (P,Σ, T 2 , p 0 , F 2 ) such that L 1 = L(A 1 ) and L 2 = L(

Suffix substitution closure, Our primary concern is to obtain a clear chara... Our primary concern is to obtain a clear characterization of which languages are recognizable by strictly local automata and which aren't. The view of SL2 automata as generators le

Mapping reducibility, (c) Can you say that B is decidable? (d) If you someh... (c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?

Ogdens lemma, proof ogdens lemma .with example i am not able to undestand ... proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .