Дана грамматика S→aB B→bB | c построить а) язык. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по теории вероятности
Дана грамматика S→aB B→bB | c построить а) язык

Дана грамматика S→aB B→bB | c построить а) язык .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Дана грамматика S→aB B→bB | c построить а) язык; б) регулярное выражение; в) граф автомата.

Решение

Потяни, чтобы посмотреть

А) Язык данной грамматики – все цепочки из нуля или более букв «b», начинающиеся с буквы «a», заканчивающиеся буквой «c»:
L = {ac, abc, abbc, abbbc, abbbbc, abbbbbc, …}.
б) Составим систему регулярных уравнений по грамматике G:
S = aB
B=bB+c
B = bB+c => B = b*c (т.к . решением уравнения X = aX+b является a*b).
Подставляем «B» в выражение для «S»:
S = aB = ab*c
Регулярное выражение, описывающее язык грамматики:
R = ab*c
в) Функция переходов автомата:
δ(S,a) = B
δ(B,b) = B
δ(B,c) = H
Конечный автомат: M({S,B,H},{a,b},δ,S,{H}),
где δ = {
{δ(S,a) = B},
{δ(B,b) = B},
{δ(B,c) = H}}.
Граф автомата:

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу