The recognizing capability of NFA and DFA 

The basic limitation of finite automata is that

If AAA is a context-free language, then there is a number ppp where, if s∈As∈As\in A  of length at least ppp, then sss may be divided into five pieces s=uvxyzs=uvxyzs = uvxyz satisfying the following condition 

Given the following automaton 

which of the following regular expressions is equivalent to the automata

Let t: N \to R^+ be a function. The time complexity class, TIME( t ( n ) ) is defined as the collection of all languages that are decidable by an O( t ( n ) ) time Turing machine.

The problem of testing whether a directed graph contains a Hamiltonian path connecting two specified nodes is solvable in polynomial time. 

The following algorithm M is a polynomial-time algorithm.

M = “On input ⟨G, s, t⟩, where G is a directed graph with nodes s and t:

1. Place a mark on node s.

2. Repeat the following until no additional nodes are marked:

3. Scan all the edges of G. If an edge (a, b) is found going from

   a marked node a to an unmarked node b, mark node b.

4. If t is marked, accept. Otherwise, reject.”

The problem defined as C = {x| x = pq, for integers p, q > 1} is polynonially verifiable. 

3SAT is polynomial time reducible to CLIQUE.

Which is the time complexity of the following Turing machine 

M = “On input string w of length n:

1. Scan across the tape and reject if a 0 is found to the right of a 1.

2. Repeat as long as some 0s and some 1s remain on the tape:

3. Scan across the tape, checking whether the total number of

   0s and 1s remaining is even or odd. If it is odd, reject.

4. Scan again across the tape, crossing off every other 0 starting with the first 0, and then crossing off every other 1 starting

   with the first 1.

5. If no 0s and no 1s remain on the tape, accept. Otherwise,

   reject .”