Банк задач по математике

Пример 3.28

Рассмотрим МП-автомат $M=(\left\{ q, p\right\} , \left\{ a, b, c\right\} , \left\{ a, b\right\} , \delta , q,\left\{ p\right\} )$ , где $\delta$ определена следующим образом:

\begin{array}{ll} \delta (q, a, \varepsilon )=\left\{ (q, a)\right\} , & \delta (p, a, a)=\left\{ (p, \varepsilon )\right\} , \\ \delta (q, b, \varepsilon )=\left\{ (q, b)\right\} , & \delta (p, b, b)=\left\{ (p, \varepsilon )\right\} , \\ \delta (q, c, \varepsilon )=\left\{ (p, \varepsilon )\right\} . & \end{array}

Определите, чему равно $L(M)$ .

?

Пример 3.29

Постройте МП-автомат, принимающий язык $\left\{ w w^{R} \mid w \in \left\{ a, b\right\}^{*}\right\}$ .

?

Пример 3.30

Постройте МП-автомат, принимающий язык

\left\{ a^{i} b^{j} c^{k} \mid i, j, k \geq 0, i+k=j\right\} .

?

Пример 3.31

Постройте МП-автомат, принимающий язык

L=\left\{ a^{i} b^{j} \mid 2 i \neq 3 j\right\} .

?

Пример 3.32

Постройте МП-автомат, принимающий язык

L=\left\{ x \in \left\{ a, b\right\} ^{*} \mid 2 \# _{a}(x) \neq 3 \# _{b}(x)\right\} .

?

Пример 3.33

Постройте МП-автомат $M$ , принимающий следующий язык:

\left\{ w \in \left\{ a, b\right\} ^{*} \mid \# _{a}(w) \leq \# _{b}(w) \leq 2 \# _{a}(w)\right\} .

?

Пример 3.34

Постройте МП-автомат $M$ , принимающий язык

L=\left\{ w \in \left\{ a, b\right\} ^{*} \mid 3 \# _{a}(w) \leq 5 \# _{b}(w) \leq 4 \# _{a}(w)\right\} .

?

Задача 3.4.1

Для каждого из следующих языков $L$ постройте МП-автомат, принимающий $L$ . Кроме того, для каждой заданной строки $x \in L$ покажите принимающий путь вычисления вашего МП-автомата на $x$ .

?

(a)

$\left\{ a^{n} b^{m} \mid m, n \geq 0, m \neq 3 n\right\} ; x=a^{2} b^{4}$ .

(b)

$\left\{ a^{n} b^{m} \mid 0 \leq 2 n \leq m \leq 3 n\right\} ; x=a^{2} b^{5}$ .

(c)

$\left\{ a^{n} b^{m} \mid 0 \leq 2 n \leq 3 m \leq 4 n-2\right\} ; x=a^{3} b^{3}$ .

(d)

$\left\{ a^{i} b^{j} c^{k} \mid i, j, k \geq 0, i+2 k=j\right\} ; x=a^{3} b^{7} c^{2}$ .

(e)

$\left\{ a^{i} b^{j} c^{k} \mid i, j, k \geq 0,2 i+3 k \leq 4 j\right\} ; x=a^{4} b^{4} c^{2}$ .

(f)

$\left\{ a^{i} b^{j} c^{k} d^{l} \mid i, j, k \geq 0, i+k \leq j+l\right\} ; x=a^{2} b^{4} c^{5} d^{3}$ .

(g)

$\left\{ a^{i} b^{j} c^{k} d^{l} \mid i, j, k \geq 0,2 i+3 k \leq 4 j+l\right\} ; x=a^{3} b^{4} c^{4} d^{5}$ .

(h)

$\left\{ w \in \left\{ a, b\right\}^{*} \mid 2 \#_{a}(w)+5 \leq 3 \#_{b}(w)\right\} ; x=a b b a b b a$ .

(i)

$\left\{ w \in \left\{ a, b\right\}^{*} \mid 2 \#_{a}(w) \leq 3 \#_{b}(w) \leq 4 \#_{a}(w)\right\} ; x=a b b a a a b$ .

(j)

$\left\{ w \in \left\{ a, b, c\right\}^{*} \mid \#_{a}(w) \leq \#_{b}(w)+3 \#_{c}(w)\right\} ; x=a a c a b b b a a$ .

(k)

$\left\{ w \in \left\{ a, b, c\right\}^{*} \mid 2 \#_{a}(w) \leq \#_{b}(w)+3 \#_{c}(w) \leq 5 \#_{a}(w)\right\} ; x=$ acabcc.

Задача 3.4.2

В примере 3.32 после завершения обработки входных символов мы переходим в одно из заключительных состояний $p_{a}$ или $p_{b}$ , если стек непуст. Покажите, что эти два отдельных состояния необходимы. А именно, предположим, что мы объединили состояния $p_{a}$ и $p_{b}$ с рисунка 3.15 в единственное заключительное состояние $p$ с инструкциями

\delta (s, \varepsilon , a)=\delta (s, \varepsilon , b)=\delta (p, \varepsilon , a)=\delta (p, \varepsilon , b)=(p, \varepsilon )

Покажите, что в этом случае новый МП-автомат будет принимать некоторые строки, не принадлежащие $L$ .

?

Задача 3.4.3

(a)(b)(c)(d)

Покажите, что каждая из следующих модификаций модели автомата с магазинной памятью эквивалентна нашему исходному определению автомата с магазинной памятью в том смысле, что класс языков, принимаемых автоматами с магазинной памятью, остаётся тем же.

?

(a)

МП-автомату разрешается заносить в стек два стековых символа за один шаг; то есть функция переходов $\delta$ имеет следующий вид:

\delta : Q \times (\Sigma \cup \left\{ \varepsilon \right\} ) \times (\Gamma \cup \left\{ \varepsilon \right\} ) \rightarrow 2^{Q \times \left(\left\{ \varepsilon \right\} \cup \Gamma \cup \Gamma ^{2}\right)}

(b)

МП-автомату разрешается заносить в стек любое число стековых символов за один шаг; то есть функция переходов $\delta$ имеет следующий вид:

\delta : Q \times (\Sigma \cup \left\{ \varepsilon \right\} ) \times (\Gamma \cup \left\{ \varepsilon \right\} ) \rightarrow 2^{Q \times \Gamma ^{*}}.

(c)

МП-автомат обязан снимать со стека верхний элемент при каждом шаге и может заносить в стек два стековых символа за один шаг; то есть функция переходов $\delta$ имеет следующий вид:

\delta : Q \times (\Sigma \cup \left\{ \varepsilon \right\} ) \times \Gamma \rightarrow 2^{Q \times \left(\left\{ \varepsilon \right\} \cup \Gamma \cup \Gamma ^{2}\right)}

(Предполагается, что МП-автомат начинает работу со специальным символом $ в стеке, то есть начальная конфигурация есть ( $s, x, \$$ ).)

(d)

МП-автомат принимает входную строку, если после завершения чтения входных символов он достигает заключительного состояния (независимо от того, пуст стек или нет); то есть МП-автомат принимает строку $x \in \Sigma^{*}$ , если $(s, x, \varepsilon ) \vdash^{*}(q, \varepsilon , \gamma )$ для некоторого $q \in F$ и некоторого $\gamma \in \Gamma^{*}$ .

Задача 3.4.4

(a)(b)

МП-автомат $M=(Q, \Sigma , \Gamma , \delta , s, F)$ называется детерминированным МП-автоматом, если ни одна конфигурация $M$ не имеет более одной последующей конфигурации (однако у незаключительной конфигурации может не быть последующей). Для каждого из примеров 3.28--3.33 выполните следующее:

?

(a)

Определите, является ли МП-автомат, заданный в примере, детерминированным.

(b)

Если ответ на (a) отрицательный, определите, существует ли эквивалентный детерминированный МП-автомат, принимающий тот же язык. Если да, приведите ваш детерминированный МП-автомат; если нет, покажите почему. [Указание: один из способов устранить (часть) недетерминизма в МП-автомате состоит в использовании модели МП-автомата из упражнения 3(c).]

Автоматы с магазинной памятью