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

Exercise:  Give a construction that converts a strictly 2-local automaton for a language L into one that recognizes the language L r . Justify the correctness of your construction.

Rubber shortnote

What is the purpose of GDTR?

Suppose A = (Σ, T) is an SL 2 automaton. Sketch an algorithm for recognizing L(A) by, in essence, implementing the automaton. Your algorithm should work with the particular automa

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

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

shell script to print table in given range

Automaton (NFA) (with ε-transitions) is a 5-tuple: (Q,Σ, δ, q 0 , F i where Q, Σ, q 0 and F are as in a DFA and T ⊆ Q × Q × (Σ ∪ {ε}). We must also modify the de?nitions of th

How useful is production function in production planning?