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

write short notes on decidable and solvable problem

We represented SLk automata as Myhill graphs, directed graphs in which the nodes were labeled with (k-1)-factors of alphabet symbols (along with a node labeled ‘?' and one labeled

What is the purpose of GDTR?

Ask question #hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhMinimum 100 words accepted#

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

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

Can v find the given number is palindrome or not using turing machine

We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also

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