Детерминированные вопросы конечного автомата

Question

У меня есть этот DFA, описанный как (Q, q1, A, N, F), где

Q = {1,2,3,4},
q1 = 1,
A = {a, b, c},
F = {2,4},
N = {
(1, a) -> 2, (1, b) -> 3,(1, с) -> 4,
(2, а) -> 2, (2, б) -> 4,
(3, а) -> 2, (3, с) -> 4,
(4, b) -> 4, (4, c) -> 4}

Итак, я нарисовал диаграмму перехода, и это выглядит хорошо,

Затем мне нужно выработать более или менее приемлемые для этого DFA следующие строки:

1. aabbcc
2. acacac
3. cabbac
4. babbab

и придумайте следующее

1. Правильно
2. Неправильно (не может перейти от -> c?)
3. Неправильно (не может перейти от c -a?)
4. Неправильно (не может перейти от b -> a)

Я не уверен на 100%, что они верны, но думаю, что они направильный путь.

Затем мне нужно описать язык, который он принимает, на английском языке, который я не считаю проблемой, но где мне нужносправка описывает этот язык с использованием математических обозначений.Не могли бы вы помочь мне понять это.

Большое спасибо за вашу помощь

Answer 1

Ваши ответы о приемлемости строк верны, это легко увидеть, если попытаться выполнить их на диаграмме.
Теперь о языке:

Во 2-й вершине мы можем закончить словами, соответствующими следующему регулярному выражению:
b?a+ - мы можем дополнительно получить b мое перемещение сначала в 3-ю вершину, а затем перейти через a, или мы можем перейти ко 2-й вершине сразу a, и там мы можем добавить столько a сколько мы хотим.

Теперь о завершении слова в 4-й вершине:

Во-первых, как мы можем достичь вершины 4?
1. Мы можем впервые достичь вершины 4, переместившись туда сразу на c или переместившись сначала к 3-ей вершине, получив b, а затем к 4-й на c. Таким образом, мы получаем строки вроде b?c
2. Мы можем достичь вершины 2 с помощью b?a+ (как описано в предыдущем случае), а затем передать b. Таким образом, мы получаем строки типа b?a+b.
Всего мы можем достичь 4-й вершины с любым словом, совпадающим с b?(a+b|c) регулярным выражением.

Теперь, добавив произвольное количество символов b и c в конце в вершине 4, мы получим ответ для этого случая:
b?(a+b|c)(bc)* 1024 *
*

Наконец, мы можем привести весь набор слов, допустимых этими словами DFA, в виде следующего регулярного выражения:

b?( a+ | (a+b|c)(bc)*? )