Я немного погуглил об этом, и ничего действительно определенного не выскочило.
Допустим, у меня есть два языка A и B.
A = {w — это подмножество {a,b,c}* такое, что предпоследний символ w равен b}
B = {w – подмножество {b,d}*, в котором последним символом является b }
Как бы это определить? Я думаю, что алфавит будет объединением обоих, что сделает его {a,b,c,d}, но кроме этого, я не знаю, как сделать из этого DFA.
Если бы кто-нибудь мог пролить свет на это, это было бы здорово.
С теоретико-множественной точки зрения каждый язык — это просто набор строк в некоторых алфавитах 1 и 2. Если вы пересекаете два языка, единственные строки, которые могут быть в результирующем наборе, — это строки, состоящие из символов в 1 2, поскольку любые символы, не входящие в этот набор должны принадлежать строкам только в одном наборе.
Что касается того, как построить DFA для этого — я бы предложил начать с ответа на этот вопрос — учитывая любой обычный язык L над алфавитом, как бы вы изменили этот DFA, чтобы он имел язык { x }, где x ? Одним из способов сделать это было бы добавить новое «мертвое состояние» с переходом к самому себе для всех символов в { x }, а затем добавить переход из каждого состояния в DFA в мертвое состояние для символа { x }. Затем вы можете использовать это, чтобы преобразовать DFA для исходных языков через 1 и 2, чтобы иметь алфавиты 1 2 . Сделав это, вы можете использовать обычный алгоритм пересечения двух DFA для вычисления их пересечения и, таким образом, получить DFA для пересечения двух языков.
Надеюсь это поможет!
