<p>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$).</p>

<p>For deciding whether $L(M)=\varnothing $ or not suppose $p$ is <a href="https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages" rel="nofollow">pumping lemma</a> number for $M$, then check for every string in set $A=\left \{ x\in \Sigma^*: |x|&lt;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|&gt;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.</p>

CC BY-SA 3.0
2015-11-15T21:31:46.803Z
2015-11-15T21:31:46.803Z
Erfan Khaniki
<p>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.  </p>

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

CC BY-SA 3.0
2015-11-16T05:02:44.083Z
2015-11-16T05:02:44.083Z
Jeffrey Shallit
<p>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</p>

CC BY-SA 3.0
2015-11-16T09:03:30.240Z
This is not a research-level question in Theoretical Computer Science, therefore it is off-topic here. You may consider asking on http://cs.stackexchange.com/ instead.
Jan Johannsen
<ds.algorithms><fl.formal-languages><automata-theory>
An algorithm that determines if regular language accepts all string of its alphabet
tzamboiv
# An algorithm that determines if regular language accepts all string of its alphabet

(Asked by: username_0 on 2015-11-15)

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

**Tags:** ds.algorithms, fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: This is not a research-level question in Theoretical Computer Science, therefore it is off-topic here. You may consider asking on http://cs.stackexchange.com/ instead.  

---

## 2 answers

### Answer by username_2 on 2015-11-15. Score: 1 | Accepted answer

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](https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages) number for $M$, then check for every string in set $A=\left \{ x\in \Sigma^\*: |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.


---

### Answer by username_3 on 2015-11-16. Score: 0

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?


---

