g | x | w | all
Bytes Lang Time Link
132JavaScript ES7250911T232937ZArnauld
380APLNARS250915T074504ZRosario
226Python 3250912T102159ZA. Helme
086Charcoal250914T072709ZNeil
06205AB1E250912T170723ZKevin Cr
362Python3250912T023212ZAjax1234

JavaScript (ES7), 132 bytes

Expects the input as a nested array, such as ['D',['D',['N','N'],'N']] for D(D(NN)N).

Returns 0, 1 or 2 for extending, non-extending and halting respectively.

a=>(k=3**(a+0).length,g=([p,q,...a])=>p?p.map?g([...p,q,...a]):g[x=p+q+a]?1:k--&&g(g[x]=[{S:q,D:[q,q],T:[q,q,q]}[p]||[],...a]):2)(a)

Try it online!

Characterization

This code uses the following characterization:

The threshold \$T\$ is set to \$3^N\$ where \$N\$ is the length of the serialized input. (What really matters is that \$N\$ is greater than the initial number of commands.)

Commented

a => (                     // a[] = input array
  k = 3 ** (a + 0).length, // k = counter
  g = ([                   // g is a recursive function taking:
    p,                     //   p = next entry from the input
    q,                     //   q = entry after next
    ...a                   //   a[] = remaining entries
  ]) =>                    //
  p ?                      // if p is defined:
    p.map ?                //   if p is an array:
      g([...p, q, ...a])   //     do a recursive call with p flattened
    :                      //   else:
      g[x = p + q + a] ?   //     define x is as the current key
                           //     if already encountered:
        1                  //       return 1
      :                    //     else:
        k-- &&             //       return 0 if k is 0
                           //       (decrement it afterwards)
        g(                 //       otherwise, do a recursive call:
          g[x] = [         //         set g[x]
            {              //
              S: q,        //         use q for 'S'
              D: [q, q],   //         use [q, q] for 'D'
              T: [q, q, q] //         use [q, q, q] for 'T'
            }[p]           //
            || [],         //         or [] for 'N'
            ...a           //         followed by the remaining entries
          ]                //
        )                  //       end of recursive call
  :                        // else:
    2                      //   return 0
)(a)                       // initial call to g

APL(NARS), 380 chars

r←f w;a;b;i;l;c;t;p;q;np;G
G←⍬
w←,w⋄r←G⍳⊂w⋄→4×⍳r≤≢G⋄G,←⊂w⋄→6
r←0⋄→0
r←1⋄→0
r←2⋄→0
np←i←1⋄p←q←r←a←b←''⋄l←≢w
→3×⍳i>l⋄a←w[i]⋄i+←1⋄→10×⍳a='('
→3×⍳i>l⋄c←w[i]⋄i+←1
→12×⍳∼c='('
p←'('⋄q←')'
→3×⍳i>l⋄c←w[i]⋄i+←1⋄np+←c=p⋄np-←c=q⋄→13×⍳np=0⋄b,←c⋄→11
b←,c
t←b⋄→15×⍳a='('⋄→5×⍳(np=1)∧(a='T')∧'T'=↑,b⋄→5×⍳(a='T')∧'ST'≡b
t←{a='N':''⋄a='S':b⋄a='D':b,p,b,q⋄a='T':b,p,b,q,p,b,q⋄'Fail'}
w←t,(i-1)↓w⋄→2

// +/ 27 4 30 7 7 7 25 31 20 12 12 55 5 61 62 15=380

f function has as input one string of chars, and return 0 for function terminate, 1 if function meets a repeat state (this means a loop), 2 if the function find a loop with no repeat state, this means that if f is not stopped it will go of out of memory in a future time.

f function puts in an array G, the state, that is each input, that would be the string array in w in each loop inside f function. If some state is repeated (find the w is already in G) than retun 1 because there is detected an infinite loop. If else function terminate it return 0. Else return 2 in the case it finds in the start of w the strings TT or T(ST) that it seems generate always differents states tha will have as effect the go out of memory in the future. I don't know if these string are the only one that generate always differents states.

The only test fail for 'T(TN)' that here result 0 instead than 1.

Here expand 'T(TN)' as

T(TN) TN(TN)(TN) NNN(TN)(TN) N(TN)(TN) (TN) TN NNN N

test:

  f¨('N')('NT')('SS')('S(TNT)')('D(D(NN)N)')
0 0 0 0 0 
  f¨('TN')('TS')('TNT')('T(NTDS)T')('T(T(T(NTDS)))')
0 0 0 0 0 
  f¨('DD')('D(SD)')('TDD')('D(NSDD)')
1 1 1 1 
  f¨('DD(TT)')('T(TN)')('S(TSD(TSD))')
1 0 1 
  f¨('TT')('ST(ST)')('NTTT')('NT(DT)')('ST(ST)N')('TTD')('D(T(TT)T)NSNS')
2 2 2 2 2 2 2 
  f 'TTD'
2
  

f ungolfed with label numbers

    r←f w;a;b;i;l;c;t;p;q;np;G
 1: G←⍬
 2: w←,w⋄r←G⍳⊂w⋄→4×⍳r≤≢G⋄G,←⊂w⋄→6
 3: r←0⋄→0
 4: r←1⋄→0
 5: r←2⋄→0
 6: np←i←1⋄p←q←r←a←b←''⋄l←≢w
 7: →3×⍳i>l⋄a←w[i]⋄i+←1⋄→10×⍳a='('
 8: →3×⍳i>l⋄c←w[i]⋄i+←1
 9: →12×⍳∼c='('
10: p←'('⋄q←')'
11: →3×⍳i>l⋄c←w[i]⋄i+←1⋄np+←c=p⋄np-←c=q⋄→13×⍳np=0⋄b,←c⋄→11
12: b←,c
13: t←b⋄→15×⍳a='('⋄→5×⍳(np=1)∧(a='T')∧'T'=↑,b⋄→5×⍳(a='T')∧'ST'≡b
14: t←{a='N':''⋄a='S':b⋄a='D':b,p,b,q⋄a='T':b,p,b,q,p,b,q⋄'Fail'}
15: w←t,(i-1)↓w⋄→2

Python 3 - 226 bytes

def f(S):
 R,H=S,[]
 while(len(R)>1):
  a,b,*q=R;n="NSDT".index(a)
  if n:R=list(b)+[b]*(n-1)+q
  elif q:R=list(q[0])+q[1:]
  else:R=q
  if R in H:return 1
  for h in H:
   if h in[R[1:],R[:len(h)]]:return 2
  H+=[R]
 return 0

Try it online!

Explanation

R is the result, H is an history of all the steps. The code runs each step, extracts the 2 first elements of the list and applies the N/S/D/T rules.

Update

Replaced if h==R[:len(h)]:return 2 by if h in[R[1:],R[:len(h)]]:return 2 to handle the case where the code expands to the left, for example with TTD.

Charcoal, 86 bytes

≔X³LΦ⭆¹θ№αιηW∧‹¹Lθ∧¬№υθ‹Lυη«⊞υθ≔⁺E⌕NSDT§θ⁰§θ¹✂θ²Lθ¹θW∧θ⁼§θ⁰⁺⟦⟧§θ⁰≔⁺§θ⁰Φθμθ»I∧‹¹Lθ∨№υθ²

Try it online! Link is to verbose version of code. Takes input as a nested character array and outputs 0 for halting, 1 for repeating and 2 for extending. Explanation:

≔X³LΦ⭆¹θ№αιη

Estimate the number of steps needed as 3ⁿ where n is the number of letters in the input. This does make the program exponentially slow for large n but fortunately not so slow that TIO can't handle the last test case.

W∧‹¹Lθ∧¬№υθ‹Lυη«

Repeat until either a) the length of the input drops below 2 b) the input repeats a previous state c) the number of previous states reaches 3ⁿ.

⊞υθ

Save the current state.

≔⁺E⌕NSDT§θ⁰§θ¹✂θ²Lθ¹θ

Use the first element to decide how many times to repeat the second.

W∧θ⁼§θ⁰⁺⟦⟧§θ⁰≔⁺§θ⁰Φθμθ

While the new first element is a list, unwrap it.

»I∧‹¹Lθ∨№υθ²

Output the final characterisation.

05AB1E, 62 bytes

[ÐDˆ˜gD_#I[€Ð€`é¤g#}g›i2q}gi€`R}ćUć¸"NSDT"Xkи渀`RììD¯€»s»åi1q

Input as a nested list of characters.
Outputs 0 for halting; 1 for unhalting repeating; 2 for unhalting extending.

Try it online or verify all test cases.

Explanation:

[                        # Start an infinite loop:
 ÐD                      #  Repeat the current state four times
                         #  (which will use the implicit input-list in the first iteration)
   ˆ                     #  Pop one copy, and add it to the global array
   ˜                     #  Pop another copy, and flatten it
    g                    #  Pop and push its length
     D                   #  Duplicate that length
      _                  #  Pop the copy, and if this length is 0:
       #                 #   Stop the infinite loop
                         #   (after which this 0 is output implicitly as result)
   I                     #  Push the input-list again
    [                    #  Start an inner infinite loop:
     €Ð                  #   Repeat each inner item three times
       €`                #   Flatten one level down
         é               #   Sort by length, so the inner lists are at the end
          ¤              #   Push the last value (without popping)
           g             #   If it's length is 1:
            #            #    Stop the inner infinite loop
    }g                   #  After this loop: pop and push the length
      ›i                 #  If the length of the current flattened list is larger:
        2                #   Push a 2
         q               #   Stop the program, after which this 2 is output implicitly
       }                 #  Close this if-statement
   g                     #  Pop the last copy, and push its length
    i                    #  If it's length is 1:
     €`R                 #   Flatten it one level down
    }                    #  Close the if-statement
     ć                   #  Extract the head of the current state
      U                  #  Pop and store this character in variable `X`
       ć                 #  Extract the head again
        ¸                #  Wrap it into a list
         "NSDT"Xk        #  Get the 0-based index of char `X` in "NSDT"
                 и       #  Repeat the wrapped list that many times
                  ć      #  Extract its head
                   ¸     #  Wrap it into a list
                    €`R  #  Flatten it one level down
                       ì #  Prepend it back to the list
        ì                #  Prepend this list back to the remainder of the state
 D                       #  Duplicate this next state
  ¯                      #  Push the global array
   €»                    #  Convert each inner list to a prettified string
     s                   #  Swap to get the current next state at the top again
      »                  #  Convert it to a similar prettified string
       åi                #  If this string is in the list:
         1               #   Push 1
          q              #   Stop the program, after which this 1 is output implicitly

Some notes:

Python3, 362 bytes

T=lambda j,r:j==r[:len(j)]and all(j[-1]==i for i in r[len(j):])
def f(s):
 q,s=[s],[]
 for i in q:
  if len(i)<2:return 0
  a,b,*c=i;V=b if str(b)[0]=='['else[b]
  if'N'==a:r=[]if[]==c else(c if str(c[0])[0]!='['else c[0]+c[1:])
  else:r=V+[b]*['S','D','T'].index(a)+c
  if r in s:return 1
  if any(T(j,r)or T(j[::-1],r[::-1])for j in s):return 2
  q+=[r];s+=[r]

Try it online!