3.2

Дополнительные примеры контекстно-свободных грамматик

[14/57%]
Показать
LaTeX
Пример 3.6
[НЕТ УСЛОВИЯ]
Пример 3.12

Найдите контекстно-свободную грамматику, порождающую язык

L={x∈{a,b}∗∣x has twice as many b’s as a’s }. L=\left\{ x \in \left\{ a, b\right\} ^{*} \mid x \text{ has twice as many b's as a's }\right\} .
?
Пример 3.13

Найдите контекстно-свободную грамматику для языка

L={x∈{a,b}∗∣#b(x)=2#a(x)+3} L=\left\{ x \in \left\{ a, b\right\} ^{*} \mid \# _{b}(x)=2 \# _{a}(x)+3\right\}
?
Пример 3.14

Найдите контекстно-свободную грамматику, порождающую язык

L={ambncpdq∣m+n=p+q} L=\left\{ a^{m} b^{n} c^{p} d^{q} \mid m+n=p+q\right\}
?
Пример 3.15

Найдите контекстно-свободную грамматику, порождающую язык

L={ambncp∣m+2n≥p} L=\left\{ a^{m} b^{n} c^{p} \mid m+2 n \geq p\right\}
?
Пример 3.16

Найдите контекстно-свободную грамматику, порождающую язык

L={ambn∣3m≤5n≤4m} L=\left\{ a^{m} b^{n} \mid 3 m \leq 5 n \leq 4 m\right\}
?
Пример 3.19

Найдите контекстно-свободную грамматику, порождающую

L={0m1n∣m≠n,m,n≥0} L=\left\{ 0^{m} 1^{n} \mid m \neq n, m, n \geq 0\right\}
?
Пример 3.20

Найдите контекстно-свободную грамматику, порождающую

L={x∈{0,1}∗∣x≠ww for any w∈{0,1}∗} L=\left\{ x \in \left\{ 0,1\right\} ^{*} \mid x \neq w w \text{ for any } w \in \left\{ 0,1\right\} ^{*}\right\}
?
Пример 3.21

Для i≥1i \geq 1 обозначим через bib_{i} двоичное представление целого числа ii (без ведущих нулей). Найдите контекстно-свободную грамматику, порождающую

L={0,1,#}∗−{b1#b2#⋯#bn∣n≥1} L=\left\{ 0,1, \# \right\} ^{*}-\left\{ b_{1} \# b_{2} \# \cdots \# b_{n} \mid n \geq 1\right\}
?
Задача 3.2.1

Для каждого из следующих языков постройте контекстно-свободную грамматику, порождающую этот язык:

?
(a)

{aibj∣2i=3j+1}\left\{ a^{i} b^{j} \mid 2 i=3 j+1\right\}.

(b)

{aibj∣2i≠3j+1}\left\{ a^{i} b^{j} \mid 2 i \neq 3 j+1\right\}.

(c)
  • {aibj∣2i≤3j≤4i}\left\{ a^{i} b^{j} \mid 2 i \leq 3 j \leq 4 i\right\}.
(d)
  • {aibj∣2i+3≤3j≤4i−2}\left\{ a^{i} b^{j} \mid 2 i+3 \leq 3 j \leq 4 i-2\right\}.
Задача 3.2.2

Для каждого из следующих языков постройте контекстно-свободную грамматику, порождающую этот язык:

?
(a)

{aibjck∣i≥k или j≥k}\left\{ a^{i} b^{j} c^{k} \mid i \geq k\text{ или }j \geq k\right\}.

(b)

{aibjck∣i+j=k}\left\{ a^{i} b^{j} c^{k} \mid i+j=k\right\}.

(c)

{aibjck∣j=i+k}\left\{ a^{i} b^{j} c^{k} \mid j=i+k\right\}.

(d)

{aibjck∣j≥i+k−3}\left\{ a^{i} b^{j} c^{k} \mid j \geq i+k-3\right\}.

(e)

{aibjck∣i+j≠k+3}\left\{ a^{i} b^{j} c^{k} \mid i+j \neq k+3\right\}.

(f)

{aibjck∣i+2j=k}\left\{ a^{i} b^{j} c^{k} \mid i+2 j=k\right\}.

(g)

{aibjck∣i+2j≡k( mod 3)}\left\{ a^{i} b^{j} c^{k} \mid i+2 j \equiv k(\bmod 3)\right\}.

(h)
  • {aibjck∣i+2j=3k}\left\{ a^{i} b^{j} c^{k} \mid i+2 j=3 k\right\}.
(i)
  • {aibjck∣i+2k≥3j}\left\{ a^{i} b^{j} c^{k} \mid i+2 k \geq 3 j\right\}.
(j)
  • {aibjck∣i+2k≤3j≤2i+3k}\left\{ a^{i} b^{j} c^{k} \mid i+2 k \leq 3 j \leq 2 i+3 k\right\}.
Задача 3.2.3

Для каждого из следующих языков постройте контекстно-свободную грамматику, порождающую этот язык:

?
(a)

{aibjckdℓ∣i+k=j+ℓ}\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid i+k=j+\ell \right\}.

(b)

{aibjckdℓ∣i+k≤j+ℓ+3}\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid i+k \leq j+\ell +3\right\}.

(c)
  • {aibjckdℓ∣i+2k=j+3ℓ}\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid i+2 k=j+3 \ell \right\}.
(d)
  • {aibjckdℓ∣i+2k≠j+3ℓ}\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid i+2 k \neq j+3 \ell \right\}.
(e)
  • {aibjckdℓ∣i+2ℓ=j+3k}\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid i+2 \ell =j+3 k\right\}.
(f)
  • {aibjckdℓ∣i+2ℓ≠j+3k}\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid i+2 \ell \neq j+3 k\right\}.
(g)

{bi#bi+1R∣bi является двоичным представлением целого числа i,i≥0}\left\{ b_{i} \# b_{i+1}^{R} \mid b_{i}\text{ является двоичным представлением целого числа }i, i \geq 0\right\}.

Задача 3.2.4

Постройте контекстно-свободную грамматику, порождающую все регулярные выражения над алфавитом {a,b}\left\{ a, b\right\}.

?
Задача 3.2.5

Для каждого из следующих языков постройте для него контекстно-свободную грамматику.

?
(a)

{xR#y∣x,y∈{0,1}∗,x является подстрокой y}\left\{ x^{R} \# y \mid x, y \in \left\{ 0,1\right\}^{*}, x\text{ является подстрокой }y\right\}.

(b)

{xR#y∣x,y∈{0,1}∗,x является подпоследовательностью y}\left\{ x^{R} \# y \mid x, y \in \left\{ 0,1\right\}^{*}, x\text{ является подпоследовательностью }y\right\}. (Строка x=x1x2⋯xkx= x_{1} x_{2} \cdots x_{k} является подпоследовательностью строки y=y1y2⋯yny=y_{1} y_{2} \cdots y_{n}, где каждый xix_{i} и каждый yjy_{j} — отдельная буква, если существуют 1≤j1<j2<⋯<jk≤n1 \leq j_{1}<j_{2}<\cdots < j_{k} \leq n, такие что yjℓ=xℓy_{j_{\ell }}=x_{\ell } для 1≤ℓ≤k1 \leq \ell \leq k.)

(c)

{amby∣y∈(a+b)n−1,n>m≥1}\left\{ a^{m} b y \mid y \in \left(a^{+} b\right)^{n-1}, n>m \geq 1\right\}.

(d)

{amby∣y∈(a+b)n−1,m>n≥1}\left\{ a^{m} b y \mid y \in \left(a^{+} b\right)^{n-1}, m>n \geq 1\right\}.

(e)

{x1#x2#⋯#xn∣x1,…,xn∈{0,1}∗,(∃1≤i<j≤n)[xi=xjR]}\left\{ x_{1} \# x_{2} \# \cdots \# x_{n} \mid x_{1}, \ldots , x_{n} \in \left\{ 0,1\right\}^{*},(\exists 1 \leq i<j \leq n) \left[x_{i}=x_{j}^{R}\right]\right\}.

(f)

{x1#x2#⋯#xn∣x1,…,xn∈{0,1}∗,(∃1≤i<j≤n)[xi≠xj]}\left\{ x_{1} \# x_{2} \# \cdots \# x_{n} \mid x_{1}, \ldots , x_{n} \in \left\{ 0,1\right\}^{*},(\exists 1 \leq i<j \leq n) \left[x_{i} \neq x_{j}\right]\right\}.

(g)
  • {0,1}∗−{www∣w∈{0,1}∗}\left\{ 0,1\right\}^{*}-\left\{ w w w \mid w \in \left\{ 0,1\right\}^{*}\right\}.
(h)
  • L=(0+1)∗−{(0n1n)n∣n≥1}L=(0+1)^{*}-\left\{ \left(0^{n} 1^{n}\right)^{n} \mid n \geq 1\right\}. [Подсказка: язык ⋃m≠n0m(1+0+)n1+\bigcup_{m \neq n} 0^{m}\left(1^{+} 0^{+}\right)^{n} 1^{+} контекстно-свободен.]