Как я могу сделать DFA следующего условия?

Question

Пожалуйста, помогите мне сделать DFA из следующих условий:

L = {ш: п (ш) по модулю 3> п _б (ш) по модулю 3},

где п (ш) представляет собой число вхождений в a ш и п _б (W) представляет собой число вхождений в b мас.

Answer 1

Прежде всего, дизайн DFA для n (a) mod3 по горизонтали и с его начальным состоянием n (b) mod3 по вертикали ..... Он будет принимать 9 состояний и отмечать состояния (a, b), где a n (a) mod3 и b представляет n (b) mod3, а затем делают состояния, имеющие первый элемент кортежа, больше второго, как конечные состояния (в этом случае будет 3) ..... надеюсь, что мой ответ поможет

Answer 2

Единственное, что нам нужно отслеживать, это количество вхождений a и b mod 3, соответственно. Есть три возможности для каждой из мод 3 и б мод 3 (0, 1 или 2, соответственно), и так как они являются независимыми, мы можем быть в общей сложности девять состояний:

• Q00: мод 3 = 0, б мод 3 = 0
• Q01: мод 3 = 1, б мод 3 = 0
• Q02: мод 3 = 2, б мод 3 = 0
• В10: мод 3 = 0, б мод 3 = 1
• Q11: мод 3 = 1, б мод 3 = 1
• Q12: мод 3 = 2, б мод 3 = 1
• Q20: мод 3 = 0, б мод 3 = 2
• Q21: мод 3 = 1, б мод 3 = 2
• Q22: мод 3 = 2, б мод 3 = 2

Это будут состояния нашего DFA. Переходы заключаются в следующем:

• из состояния Qij, переход к Qij 'на входе а, где J' = (J + 1) по модулю 3
• из состояния Qij, переход к qi'j на входе б , где i '= (i + 1) mod 3

Это дает нам в общей сложности 18 переходов.

Мы хотим принять, когда мод 3> b mod 3; то есть:

• состояние Qij принимает тогда и только тогда J> Я

Это дает нам 3, принимающие государства.

Наконец, наше начальное состояние возникает, когда мы видели нулевые экземпляры любого символа; то есть:

• начальное состояние Q00

В настоящее время мы полностью определили DFA для этого языка.