-2
$\begingroup$

Let $L$ be a regular language with the alphabet $\Sigma$. I'm trying to find an algorithm to tell whether $L=\Sigma^{*}$, whether $L$ accepts all strings in its alphabet. I think this algorithm uses converting the language to a DFA, but I'm not sure what to do from there. I have only recently began learning about regular languages and complexity, so help would be appreciated

$\endgroup$

closed as off-topic by Lev Reyzin Jan 26 '16 at 2:34

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ This is not a research-level question in Theoretical Computer Science, therefore it is off-topic here. You may consider asking on cs.stackexchange.com instead. $\endgroup$ – Jan Johannsen Nov 16 '15 at 9:03
0
$\begingroup$

If we had an algorithm that decide whether $L(M)=\varnothing $ or not then it can be used for deciding whether for some $DFA$ like $M$ $L(M)=\Sigma^*$ or not,(by creating the DFA $M'$ from $M$ such that $L(M)=L(M')^c$).

For deciding whether $L(M)=\varnothing $ or not suppose $p$ is pumping lemma number for $M$, then check for every string in set $A=\left \{ x\in \Sigma^*: |x|<p+1 \right \}$ whether it is in $L(M)$ or not, If $A\cap L(M)\not =\varnothing $ then $L(M)\not = \varnothing $. If $A\cap L(M)=\varnothing $ then $L(M)=\varnothing $, because if there exists a string $x$ such that $|x|>p$ and $x\in L(M)$ then by pumping down on $x$ we can reach a string like $y$ such that $y\in A\cap L(M)$ and this leads to contradiction.

$\endgroup$
0
$\begingroup$

The very first thing you need to think about is, how are you "given" a regular language? A language L could contain infinitely many strings, so clearly you are not "given" L itself.

Are you given L as a regular expression, finite automaton, right-linear grammar, two-way automaton, or what?

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.