Дана регулярная грамматика S -> aS | bA; A -> a | b; определите, является ли язык, задаваемый грамматикой, регулярным и однозначным, постройте ДКА или объясните, почему это невозможно, и приведите примеры строк, принадлежащих языку

14 Ноя в 10:42
4 +1
0
Ответы
1
Грамматика
S→aS∣bA,A→a∣bS\to aS\mid bA,\qquad A\to a\mid bSaSbA,Aab является праволинейной, значит язык регулярен. Грамматика однозначна: для каждой строки единственная левая вывода (нельзя выбрать альтернативу иначе, чем повторить S→aSS\to aSSaS нужное число раз, затем S→bAS\to bASbA, затем A→aA\to aAa или A→bA\to bAb).
Язык можно описать как
L={ anba, anbb∣n≥0 }. L=\{\,a^n b a,\; a^n b b \mid n\ge 0\,\}.
L={anba,anbbn0}.

ДКА, распознающий LLL:
M=(Q,Σ,δ,q0,F), M=(Q,\Sigma,\delta,q_0,F),
M=(Q,Σ,δ,q0 ,F),
где
Q={q0,q1,q2,qd},Σ={a,b},q0 — старт,F={q2}, Q=\{q_0,q_1,q_2,q_d\},\quad \Sigma=\{a,b\},\quad q_0\ \text{— старт},\quad F=\{q_2\},
Q={q0 ,q1 ,q2 ,qd },Σ={a,b},q0 старт,F={q2 },
и переходы
δ(q0,a)=q0,δ(q0,b)=q1,δ(q1,a)=q2,δ(q1,b)=q2,δ(q2,a)=qd,δ(q2,b)=qd,δ(qd,a)=qd,δ(qd,b)=qd. \begin{aligned}
&\delta(q_0,a)=q_0,\quad \delta(q_0,b)=q_1,\\
&\delta(q_1,a)=q_2,\quad \delta(q_1,b)=q_2,\\
&\delta(q_2,a)=q_d,\quad \delta(q_2,b)=q_d,\\
&\delta(q_d,a)=q_d,\quad \delta(q_d,b)=q_d.
\end{aligned}
δ(q0 ,a)=q0 ,δ(q0 ,b)=q1 ,δ(q1 ,a)=q2 ,δ(q1 ,b)=q2 ,δ(q2 ,a)=qd ,δ(q2 ,b)=qd ,δ(qd ,a)=qd ,δ(qd ,b)=qd .

Примеры строк из языка: для n=0n=0n=0ba, bbba,\; bbba,bb; для n=1n=1n=1aba, abbaba,\; abbaba,abb; для n=3n=3n=3aaaba, aaabbaaaba,\; aaabbaaaba,aaabb.
14 Ноя в 11:36
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир