Приостановить поток, пока метод и все потоки внутри не закончат свою работу?

Для блокировки до тех пор, пока поток t не завершится, вы можете использовать Thread.Join.

t.Join();

Это переводит основной поток в состояние IDLE до тех пор, пока поток t не завершится. Это означает, что вам придется отслеживать все потоки, созданные внутри цикла foreach, а затем присоединяться к ним один за другим.

Лучшим способом было бы использовать TPL Task<T> вместо прямого использования потоков. Ваш код будет выглядеть примерно так:

Task ThreadEval(string s, State q)
{
    //...

    List<Task> tasks = new List<Task>();

    for (int i = 0; found && !accepted && i < s.Length; i++)
    {
        found = false;
        foreach (Transition t in current.transitions)
            if (t.symbol == s[i])
            {
                tasks.Add(
                    Task.Run(
                        () => await ThreadEval(s.Substring(i+1), t.to)));
                found = true;
            }
     }

    return Task.WhenAll(tasks);
}

await ThreadEval(...);

1. Измените подпись, чтобы она возвращала Task вместо void
2. Создайте список всех запущенных задач
3. Task.WhenAll создаст новую задачу, которая будет помечена как завершенная, когда все задачи в списке tasks будут отмечены как завершенные. Верните эту задачу.

Затем вызывающий объект await ThreadEval.

Написал небольшой пример, чтобы помочь вам понять, как это можно сделать https://dotnetfiddle.net/2Djdh7

По сути, вы можете использовать метод Join() для ожидания завершения потока, а с помощью метода ForEach() для списка потоков вы можете дождаться завершения всех потоков в одной строке.

public class Program
{
    public static void Main(string[] args)
    {
        List<int> list = new List<int>();
        list.AddRange(new int[] {10, 200, 300, 400, 234 });

        // create a bunch of threads
        List<Thread> threads = new List<Thread>();
        list.ForEach(x => threads.Add(new Thread(() => ThreadMethod(x))));

        // start them
        threads.ForEach(x => x.Start());

        // wait for them to finish
        threads.ForEach(x => x.Join());

        // this will not print untill all threads have completed
        Console.WriteLine("Done");
    }

    private static void ThreadMethod(int i)
    {
        Thread.Sleep(i);
        Console.WriteLine("Thread: " + i);
    }
}

Выход:

Thread: 10
Thread: 200
Thread: 234
Thread: 300
Thread: 400
Done

Думаю, здесь вам поможет шаблон async/await. Затем вы можете сделать что-то вроде:

List<Task> runningEvals = new List<Task>();

async Task ThreadEval(string s, State q)
{            
    if (s.Length == 0 && q.IsFinal)
    {
        Task.WaitAll(runningEvals.ToArray()); // wait for all tasks to finish
        runningEvals.Clear();

        accepted = true;
        return;
    }

    bool found = true;            
    State current = q;

    for (int i = 0; found && !accepted && i < s.Length; i++)
    {
        found = false;
        foreach (Transition t in current.transitions)
            if (t.symbol == s[i])
            {
                // start a task and add it to the "running tasks" list
                var task = Task.Run(async () => await ThreadEval(s.Substring(i+1), t.to));
                runningEvals.Add(task);
                found = true;
            }
     }
}

ВНИМАНИЕ: Это не проверенный код (и определенно не "сохраняющий потоки" из-за "общих List<Task>"), но он должен только указать вам направление.

Это можно назвать «асинхронным» через:

await ThreadEval(s, StartState);

или если вы не можете пройти "асинхронно до конца" (и только тогда):

ThreadEval(s, StartState).Wait();