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
let G=(V,T,S,P) where V={a,b,A,B,S}, T={a,b},S the start symbol and P={S->Aba, A->BB, B->ab,AB->b} 1.show the derivation sentence for the string ababba 2. find a sentential form

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.

c program to convert dfa to re

A Turing machine is a theoretical computing machine made-up by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine having of a line of


1. An integer is said to be a “continuous factored” if it can be expresses as a product of two or more continuous integers greater than 1. Example of continuous factored integers

The fact that regular languages are closed under Boolean operations simpli?es the process of establishing regularity of languages; in essence we can augment the regular operations

The Recognition Problem for a class of languages is the question of whether a given string is a member of a given language. An instance consists of a string and a (?nite) speci?cat

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one