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
i have some questions in automata, can you please help me in solving in these 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

Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG too. Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the sec

what are the advantages and disadvantages of wearable computers?

Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

1. Does above all''s properties can be used to prove a language regular? 2..which of the properties can be used to prove a language regular and which of these not? 3..Identify one

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

While the SL 2 languages include some surprisingly complex languages, the strictly 2-local automata are, nevertheless, quite limited. In a strong sense, they are almost memoryless

how to understand DFA ?

De?nition (Instantaneous Description) (for both DFAs and NFAs) An instantaneous description of A = (Q,Σ, δ, q 0 , F) , either a DFA or an NFA, is a pair h q ,w i ∈ Q×Σ*, where