Дана регулярная грамматика S -> aS | bA; A -> a | b; определите, является ли язык, задаваемый грамматикой, регулярным и однозначным, постройте ДКА или объясните, почему это невозможно, и приведите примеры строк, принадлежащих языку
Грамматика \(S\to aS\mid bA,\qquad A\to a\mid b\) является праволинейной, значит язык регулярен. Грамматика однозначна: для каждой строки единственная левая вывода (нельзя выбрать альтернативу иначе, чем повторить \(S\to aS\) нужное число раз, затем \(S\to bA\), затем \(A\to a\) или \(A\to b\)). Язык можно описать как \[ L=\{\,a^n b a,\; a^n b b \mid n\ge 0\,\}. \] ДКА, распознающий \(L\): \[ M=(Q,\Sigma,\delta,q_0,F), \] где \[ Q=\{q_0,q_1,q_2,q_d\},\quad \Sigma=\{a,b\},\quad q_0\ \text{— старт},\quad F=\{q_2\}, \] и переходы \[ \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} \] Примеры строк из языка: для \(n=0\) — \(ba,\; bb\); для \(n=1\) — \(aba,\; abb\); для \(n=3\) — \(aaaba,\; aaabb\).
\(S\to aS\mid bA,\qquad A\to a\mid b\)
является праволинейной, значит язык регулярен. Грамматика однозначна: для каждой строки единственная левая вывода (нельзя выбрать альтернативу иначе, чем повторить \(S\to aS\) нужное число раз, затем \(S\to bA\), затем \(A\to a\) или \(A\to b\)).
Язык можно описать как
\[
L=\{\,a^n b a,\; a^n b b \mid n\ge 0\,\}.
\]
ДКА, распознающий \(L\):
\[
M=(Q,\Sigma,\delta,q_0,F),
\]
где
\[
Q=\{q_0,q_1,q_2,q_d\},\quad \Sigma=\{a,b\},\quad q_0\ \text{— старт},\quad F=\{q_2\},
\]
и переходы
\[
\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}
\]
Примеры строк из языка: для \(n=0\) — \(ba,\; bb\); для \(n=1\) — \(aba,\; abb\); для \(n=3\) — \(aaaba,\; aaabb\).