Дана регулярная грамматика S -> aS | bA; A -> a | b; определите, является ли язык, задаваемый грамматикой, регулярным и однозначным, постройте ДКА или объясните, почему это невозможно, и приведите примеры строк, принадлежащих языку
Грамматика S→aS∣bA,A→a∣bS\to aS\mid bA,\qquad A\to a\mid bS→aS∣bA,A→a∣b
является праволинейной, значит язык регулярен. Грамматика однозначна: для каждой строки единственная левая вывода (нельзя выбрать альтернативу иначе, чем повторить S→aSS\to aSS→aS нужное число раз, затем S→bAS\to bAS→bA, затем A→aA\to aA→a или A→bA\to bA→b). Язык можно описать как L={ anba, anbb∣n≥0 }.
L=\{\,a^n b a,\; a^n b b \mid n\ge 0\,\}. L={anba,anbb∣n≥0}. ДКА, распознающий 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=0 — ba, bbba,\; bbba,bb; для n=1n=1n=1 — aba, abbaba,\; abbaba,abb; для n=3n=3n=3 — aaaba, aaabbaaaba,\; aaabbaaaba,aaabb.
S→aS∣bA,A→a∣bS\to aS\mid bA,\qquad A\to a\mid bS→aS∣bA,A→a∣b является праволинейной, значит язык регулярен. Грамматика однозначна: для каждой строки единственная левая вывода (нельзя выбрать альтернативу иначе, чем повторить S→aSS\to aSS→aS нужное число раз, затем S→bAS\to bAS→bA, затем A→aA\to aA→a или A→bA\to bA→b).
Язык можно описать как
L={ anba, anbb∣n≥0 }. L=\{\,a^n b a,\; a^n b b \mid n\ge 0\,\}.
L={anba,anbb∣n≥0}.
ДКА, распознающий 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=0 — ba, bbba,\; bbba,bb; для n=1n=1n=1 — aba, abbaba,\; abbaba,abb; для n=3n=3n=3 — aaaba, aaabbaaaba,\; aaabbaaaba,aaabb.