Создание DFA, который принимает язык с союзом

Question

Я пытаюсь выяснить, как создать DFA, который принимает язык с алфавитом ∑ = {a, b}.Это часть проблемы с домашним заданием, и я думаю, что у меня есть базовое представление о том, как создавать простые DFA, но я не могу обернуть голову вокруг символа объединения и, что более важно, каково значение u?

Answer 1

u представляет строку любой длины (включая 0), содержащую a с и b с в любом порядке.Вот что означает условие, что u является элементом ∑ *.

В общем случае вы создадите DFA, создав NFA, у которого начальное состояние имеет более одного выхода, и затем выполните ε-замыкание в NFA.В этом случае два начальных перехода являются взаимоисключающими, поэтому вы можете просто объединить начальные состояния двух DFA.

Это, вероятно, лучше объяснено в вашем учебнике и / или в примечаниях к лекциям.