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
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

how to understand DFA ?

We have now de?ned classes of k-local languages for all k ≥ 2. Together, these classes form the Strictly Local Languages in general. De?nition (Strictly Local Languages) A langu

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.

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

A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi



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.