Sketch an algorithm for recognizing language, Theory of Computation

Suppose A = (Σ, T) is an SL2 automaton. Sketch an algorithm for recognizing L(A) by, in essence, implementing the automaton. Your algorithm should work with the particular automaton being given as a table of some sort, so that it can be easily generalized for the next part of the exercise. Your algorithm may halt as soon as it detects that the input is not in the language.

Posted Date: 3/21/2013 5:47:37 AM | Location : United States







Related Discussions:- Sketch an algorithm for recognizing language, Assignment Help, Ask Question on Sketch an algorithm for recognizing language, Get Answer, Expert's Help, Sketch an algorithm for recognizing language Discussions

Write discussion on Sketch an algorithm for recognizing language
Your posts are moderated
Related Questions

Ask question #Minimum 100 words accepte

constract context free g ={ a^n b^m : m,n >=0 and n

I want a proof for any NP complete problem


design an automata for strings having exactly four 1''s

Given any NFA A, we will construct a regular expression denoting L(A) by means of an expression graph, a generalization of NFA transition graphs in which the edges are labeled with

As de?ned the powerset construction builds a DFA with many states that can never be reached from Q′ 0 . Since they cannot be reached from Q′ 0 there is no path from Q′ 0 to a sta

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

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