690 views

2 Answers

0 votes
0 votes

a) INFINITEDFA is decidable

The language accepted by a DFA M with n states is infinite if and only if M accepts a string of length k, where n≤k<2n

This makes the decision problem simple: just try all strings of length at least nn and less than 2n and answer "yes" if M accepts one of them and "no" if there's no string in that range that's accepted.

if a DFA with n states accepts a string of length n, itself is a sufficient condition to tell that a DFA accepts an infinite language, but we are using upper limit of 2n to stop our testing, if DFA accepts finite language we will keep on testing.

0 votes
0 votes
For the above problem we can design a Decider Turing Machine as follows:

    T = "On input <A> where A is a DFA"
        1. Staring from the initial state it mark each state it visited and proceed through all the edge of using any graph traversal algorithm , if it find any loop in the process then "Accepted"
        2. "rejected"

Related questions