Universality problem, Theory of Computation

The Universality Problem is the dual of the emptiness problem: is L(A) = Σ∗?

It can be solved by minor variations of any one of the algorithms for Emptiness or (with a little less work) it can simply be reduced to Emptiness.

Theorem (Universality) The Universality Problem for Regular Languages is decidable.

Proof: L(A) = Σ*⇔ L(A) = ∅. As regular languages are effectively closed under complement we can simply build the DFA for the complement of L(A) and ask if it recognizes the empty language.

Posted Date: 3/21/2013 1:55:24 AM | Location : United States







Related Discussions:- Universality problem, Assignment Help, Ask Question on Universality problem, Get Answer, Expert's Help, Universality problem Discussions

Write discussion on Universality problem
Your posts are moderated
Related Questions
Exercise Show, using Suffix Substitution Closure, that L 3 . L 3 ∈ SL 2 . Explain how it can be the case that L 3 . L 3 ∈ SL 2 , while L 3 . L 3 ⊆ L + 3 and L + 3 ∈ SL

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

The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

design a tuning machine for penidrome

The generalization of the interpretation of strictly local automata as generators is similar, in some respects, to the generalization of Myhill graphs. Again, the set of possible s


Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici

S-->AAA|B A-->aA|B B-->epsilon

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

what are the advantages and disadvantages of wearable computers?