2
$\begingroup$

Is the following language decidable? $$L = \{A : \text{A is a DFA and } |L(A)| \ge 2\}$$

$\endgroup$
  • 4
    $\begingroup$ What did you try? Where did you get stuck? Did you, for example, try to think about what an automaton would have to look like if it accepted more than one string? We're happy to help with conceptual problems but just solving homework-style exercises for you is unlikely to really help you. $\endgroup$ – David Richerby Jun 14 '17 at 11:54
  • $\begingroup$ I considered enumerating all of $\Sigma^*$ and accepting if at least two strings were accepted by $A$, but realised that would only recognise $L$ and not decide it. (It's study for an upcoming exam, not homework) $\endgroup$ – Brandon Presley Jun 14 '17 at 12:06
2
$\begingroup$

First remove dead states(those which do not lead to accept states). Then run depth first search. If all accepts states are not reachable or there is a single path leading to an accept state then REJECT. If there are two different paths leading to an accept state (or accept states) then ACCEPT. If there is a cycle including a state from which an accept is reachable also ACCEPT.

$\endgroup$
  • $\begingroup$ Please consider not posting full answers to things that look like homework exercises. $\endgroup$ – David Richerby Jun 14 '17 at 11:55
  • $\begingroup$ Sorry. I got you. $\endgroup$ – fade2black Jun 14 '17 at 11:59
2
$\begingroup$

More generally, suppose that you have a class of languages (represented implicitly in some way) supporting the following operations:

  • Given a language $L$, decide whether $L = \emptyset$.
  • Given a language $L$ and a word $x$, decide whether $x \in L$.
  • Given a language $L$ and a word $x \in L$, construct $L \setminus \{x\}$.

Then you can decide whether $|L| \geq k$ for any $k \geq 0$. You can similarly decide whether $|L| \leq k$ and whether $|L| = k$. If you can also solve the following problem, then you can compute $|L|$:

  • Given a language $L$, decide whether $L$ is infinite.

The class of regular languages, represented as DFAs, supports all of these operations (exercise!), hence you can compute $|L|$ for a regular language $L$ given as a DFA, and in particular solve your problem.

$\endgroup$
2
$\begingroup$

Here is another approach. Suppose that the DFA has state set $Q$, accepting states $F$, initial state $q_0$, and transition function $\delta$. Let $M$ be the $Q \times Q$ matrix defined as follows: $M(q_2,q_1)$ is the number of symbols $\sigma$ such that $\delta(q_1,\sigma) = q_2$. Let $s$ be the indicator vector of $q_0$, and let $f$ be the indicator vector of $F$. Then the number of words of length $n$ accepted by the DFA is $f' M^n s$, and so the total number of words accepted by the DFA is $$ \sum_{n \geq 0} f'M^ns = f' \left(\sum_{n \geq 0} M^n\right) s = f' (I-M)^{-1} s, $$ where the latter formula is valid if $\|M\| < 1$, which will be the case if the language accepted by the DFA is finite, assuming all states are accessible (reachable from $q_0$) and co-accessible (can reach $F$).

A similar approach without inverting any matrices is to compute $c_n = f'M^n s$ for $0 \leq n < 2|Q|$. It is known that the language accepted by the DFA is infinite if and only if $c_{|Q|} + \cdots + C_{2|Q|-1} > 0$, and otherwise the total number of words in the language is $c_0 + \cdots + c_{|Q|-1}$. Note that the sequence $c_n$ can be computed using only matrix-vector multiplication, which is more efficient than matrix multiplication.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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