logo
ОТВЕТЫ НА ГОСы (все ответы)

1. Регулярные языки и конечные автоматы. (та)

Согласно Хомскому регулярная грамматика - это грамматика, продукции которой имеют вид : а) А а | aB – правосторонняя; б) А а | Bа – левосторонняя; где a  V ; A ,B  W. Регулярные языки – это языки, порожденные регулярными грамматиками. Регулярная грамматика соответствует конечному автомату. Теорема. Для любого непустого языка L порождаемого регулярной грамматикой G3, существует Конечный Автомат К, возможно недетерминированный, представляющий (порождающий и распознающий) язык L. Конечным автоматом называется формальная система К которая задается 5-ю объектами К=<A, Q, B, ,  >, где A - входной алфавит ={a1, a2, a3, … , am}, Q - алфавит состояний {q1, q2, q3, … , qn}, B - выходной алфавит {b1, b2, b3, ... , b k}, - функция переходов; : QAQ;  - функция выходов автомата ; : QAB .

Конечным детерминированным автоматом типа Мили называется совокупность пяти объектов ,где S, X и Y — конечные непустые множества, а δ и λ — отображения вида: и со связью элементов множеств S, X и Y в абстрактном времени T = {0, 1, 2, …} уравнениями:

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y(t) обнаруживается только при наличии символа во входном канале x(t). Функциональная схема не отличается от схемы абстрактного автомата. Зависимость выходного сигнала только от состояния представлена в автоматах типа Мура. В автомате Мура функция выходов определяет значение выходного символа только по одному аргументу — состоянию автомата.

Конечным детерминированным автоматом типа Мура называется совокупность пяти объектов:

где S, X, Y и δ — соответствуют определению автомата типа Мили, а μ является отображением вида: μ : S → Y,

с зависимостью состояний и выходных сигналов во времени уравнением:

. Автоматом Мура называется конечный автомат, у которого функции выхода не зависят от входного знака (зависит только от состояния автомата).K=<A, Q, B,  >. Для любого qi принадлежащего Q и для любого aj1, aj2 принадлежащего A. ( qi, aj1) = (qi, aj2) - это означает что функция  является одноаргументной функцией и зависит только лишь от состояния автомата. Обозначим эту функцию  Km=< A, Q, B, > ,  : Q  B (иногда  называют - функцией отметок). Состояние выхода можно записать в самой системе. Для любого автомата Мили К существует неотличимый от него автомат Мура Кm.