2 автомата

[asdf]

Здравейте. Дали ще може някой да помогне с построяването на следните 2 автомата:
1) автомат разпознаващ [tex]L = \{ w \in \{0,1\}*[/tex]| броят на буквите 0 в w се дели на 3 }
2) автомат разпознаващ всички думи, в които от 4 последователни букви поне една е 1
По принцип за 2рата измислих някакво решение но е доста безумно. Строя автомати разпознаващи [tex](1000)^{+},(0100)^{+},(0010)^{+},(0001)^{+}, (1100)^{+}[/tex] и тн на останалите и им правя обединение, но съм сигурен, че трябва да има и нещо по-хитро. По първата също мислех, че имам идея, но се оказа, че не работи

[ptj]

Минали са доста години откакто човърках разни автоматчета, но май още помня нещо.

1.)За първата задача и за други подобни, след като един автомат се иска да брои нещо, то се изисква да имаш толкова междинни състояния. Идеята е те да циклят в себе си с това, което не се брои, а при преминаването към следващото състояние да става само със съотвената буква от броящата се дума. Финално състояние е само това, в което се завършва броимата дума, цъкъл се постига като от финалното състояние влезем във 2-рото състоянието (след първата броима буква) посредством първата буква от думата. Ако езика включва празната дума, може да обединиш първото и крайното състояния, т.е. да станат с едно по-малко.

2. Тук условието не е много точно. Може би се има в предвид от всеки 4 последователни букви поне една да е 1. Освен това не е казано дали думи с по малко от 4 символа влизат в езика.

Нищо сложно. Езика не трябва да съдържа 4-тири последователни нули. Може да го конструираш по 2 начина :
1.) Директно. Тогава всеки цикъл в твоя автомат може да има максимум 3 нули.
2.) Построяваш автомата разпознаващ език съдържащ поне 4 нули във всяка дума. После си поглеждаш теоремите как се посроява автомат за допълнението на даден език.

За 1.) автомата е с 3 състояния, всички са финални. Във всяко едно се цикли с 1-ца. От 1-во към 2-ро се минава с 1. От 2-ро към 3-то с 1. От 3-то към първо с 1. Това би трябвало да е.