Algorithm for the universal recognition problem, Theory of Computation

Sketch an algorithm for the universal recognition problem for SL2. This takes an automaton and a string and returns TRUE if the string is accepted by the automaton, FALSE otherwise. Assume the automaton is given just as a sequence of pairs of symbols and that the automaton and string are both over the same language. Give an argument justifying the correctness of your algorithm.

Posted Date: 3/21/2013 5:48:30 AM | Location : United States







Related Discussions:- Algorithm for the universal recognition problem, Assignment Help, Ask Question on Algorithm for the universal recognition problem, Get Answer, Expert's Help, Algorithm for the universal recognition problem Discussions

Write discussion on Algorithm for the universal recognition problem
Your posts are moderated
Related Questions
One of the first issues to resolve, when exploring any mechanism for defining languages is the question of how to go about constructing instances of the mechanism which define part

Describe the architecture of interface agency

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

While the SL 2 languages include some surprisingly complex languages, the strictly 2-local automata are, nevertheless, quite limited. In a strong sense, they are almost memoryless

We now add an additional degree of non-determinism and allow transitions that can be taken independent of the input-ε-transitions. Here whenever the automaton is in state 1



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

Computation of a DFA or NFA without ε-transitions An ID (q 1 ,w 1 ) computes (qn,wn) in A = (Q,Σ, T, q 0 , F) (in zero or more steps) if there is a sequence of IDs (q 1