retagged by
3,504 views
13 votes
13 votes

Define the language $\text{INFINITE}_{DFA}\equiv \{(A)\mid A \text{ is a DFA and } L(A) \text{ is an infinite language}\},$ where $(A)$ denotes the description of the deterministic finite automata (DFA).Then which of the following about $\text{INFINITE}_{DFA}$ is TRUE:

  1. It is regular. 
  2. It is context-free but not regular. 
  3. It is Turing decidable (recursive).
  4. It is Turing recognizable but not decidable.
  5. Its complement is Turing recognizable but it is not decidable.
retagged by

3 Answers

11 votes
11 votes
We can directly eliminate option A and B as we need to do some computation which is beyond (in this case) the capacity of the FSM and the PDA.

Let's understand what does 'encoding' of a DFA means. It is nothing but a string of 1's and 0's which on reading, you will get the complete idea about DFA, that is how many states it has, which is the start stare, which are final states, all transitions etc. Basically, we are 'encoding' whatever we know about the given DFA in 0's and 1's. There is no fixed procedure for how this encoding should be. You can do it in whichever way you like.

Now the question is on taking a string of 1's and 0's (The description of a DFA) as the input, can we write a C program which will print "YES" when the FSM corresponding to that string accepts the infinite language and prints "NO" otherwise. The answer is YES we can write such a program. We will be checking for the "loops" in the FSM corresponding to the given string as the existence of a loop and a valid final state implies that the FSM accepts infinite language. (We can use the logic of finding a cycle in the directed graphs which can be done in O(V+E) time for the graphs. ) So this is a decidable problem.
1 votes
1 votes
As per my knowledge question is asking us "is there any machine which can tell us that a given dfa accept infinite language"

We know that finite and infiniteness of dfa it's decidiablity

So corresponding Turing machine will either give Answer yes or no

This Infinite DFA is Turing decidiablity
0 votes
0 votes

To show that INFINITEDFA is decidable, meaning to construct a TM $M$ that decides INFINITEDFA.

This means that for all DFA's  A we want

• If L(A) is an infinite language then M(<A>) accepts

• If L(A) is a finite language then M(<A>) rejects.

To construct a TM M we use the following claim.

Claim: Suppose A is a DFA with p states and alphabet Σ.

                Let BA = { w ∈ Σ* : w ∈ L(A) and p ≤ |w| ≤ 2p } .

Then L(A) is infinite if and only if BA != ∅.

This means that to test whether or not L(A) is infinite, we need only test whether or not BA is empty. The latter can be done using the machine Mdfa since BA is a finite set.

So, just run Mdfa on the strings w ∈ L(A) such that p ≤ |w| ≤ 2p.

If Mdfa accepts at least one string w then the DFA $A$ is accepted by M otherwise rejected.

Hence INFINITEDFA is Turing decidable (recursive) .

Now, I prove the claim.

In the first part of the proof, we assume that BA != ∅.

We want to show that L(A) is infinite. Note that the number of states p in the DFA is the p of the Pumping Lemma applied to the regular language L(A).

Since BA is non-empty, there is some string s ∈ BA. By definition of BA we have s ∈ L(A) and |s| ≥ p, so there exist x, y, z such that s = xyz where y is non empty and |xy| <= p.

So, we get that xyi z ∈ L(A) for all i ≥ 0. This means that L(A) is infinite.

In the second part of the proof, we assume that L(A) is infinite.

We want to show that BA != ∅. Let s be a shortest string in L(A) such that |s| ≥ p. (Such an s exists since L(A) is infinite.)

If |s| ≤ 2p then s ∈ BA so we have shown BA != ∅.

Now, suppose towards a contradiction that |s| > 2p. Apply the Pumping Lemma to the regular language L(A) to write s = xyz such that the three conditions of the Pumping Lemma hold.

Setting i = 0 in the first condition tells us that xz ∈ L(A).

Again we have |y| ≤ p.

So |xz| = |s| − |y| > 2p − p = p, meaning xz is a string in L(A) with length strictly greater than p, but is shorter than s.

This contradicts the assumption that s was the shortest such string.

Answer:

Related questions

4 votes
4 votes
1 answer
2