Finite languages and strictly local languages, Theory of Computation

Theorem The class of ?nite languages is a proper subclass of SL. Note that the class of ?nite languages is closed under union and concatenation but SL is not closed under either. Nevertheless, this does not contradict the fact that every ?nite language is SLk, for some k. All it says is that the counterexamples that establish non-closure of SL under union and concatenation must involve non-?nite languages. (You should verify the fact that they do.)

Posted Date: 3/22/2013 2:06:20 AM | Location : United States







Related Discussions:- Finite languages and strictly local languages, Assignment Help, Ask Question on Finite languages and strictly local languages, Get Answer, Expert's Help, Finite languages and strictly local languages Discussions

Write discussion on Finite languages and strictly local languages
Your posts are moderated
Related Questions
Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the

how to find whether the language is cfl or not?

. On July 1, 2010, Harris Co. issued 6,000 bonds at $1,000 each. The bonds paid interest semiannually at 5%. The bonds had a term of 20 years. At the time of issuance, the market r


De?nition Deterministic Finite State Automaton: For any state set Q and alphabet Σ, both ?nite, a ?nite state automaton (FSA) over Q and Σ is a ?ve-tuple (Q,Σ, T, q 0 , F), w

What are the benefits of using work breakdown structure, Project Management

can you plz help with some project ideas relatede to DFA or NFA or anything

how to prove he extended transition function is derived from part 2 and 3

s-> AACD A-> aAb/e C->aC/a D-> aDa/bDb/e

Find a regular expression for the regular language L={w | w is decimal notation for an integer that is a multiple of 4}