Как доказать, что язык не является контекстом?

cs.stackexchange https://cs.stackexchange.com/questions/265

Вопрос

Мы узнали о классе языков без контекста $ mathrm {cfl} $. Характеризуется обоими Контекстные грамматики а также Автоматы отжимания Так что легко показать, что данный язык не имеет контекста.

Как мне показать наоборот, хотя? Моя та была непреклонна, что для этого мы должны были бы показать все грамматики (или автоматы), что они не могут описать язык под рукой. Это кажется большой задачей!

Я читал о какую -то накачанную лемму, но это выглядит очень сложно.

Это было полезно?

Решение

Насколько мне известно перекачивая лемму является на сегодняшний день Самая простая и наиболее используемая техника. Если вам это трудно, попробуйте обычная версия Во -первых, это не так уж плохо. Есть некоторые другие средства для языков, которые далеки от контекста. Например, неразрешимые языки тривиально не свободны от контекста.

Тем не менее, я также заинтересован в других методах, чем накачанная лемма, если есть.

РЕДАКТИРОВАТЬ: Вот пример для насосной леммы: Предположим, что язык $ l = {a^k mid k ∈ P } $ бесплатно ($ p $ - набор основных чисел). Накачанная лемма имеет много $ ∃ ∃ ∀ $ Quantifiers, поэтому я сделаю это немного похожим на игру:

  1. Насосная лемма дает вам $ p $
  2. Вы даете слово $ s $ на языке длины не менее $ p $
  3. Насосная лемма переписывает это так: $ s = uvxyz $ с некоторыми условиями ($ | vxy | ≤p $ и $ | vy | ≥1 $)
  4. Вы даете целое число $ n≥0 $
  5. Если $ uv^nxy^nz $ не в $ l $, вы выигрываете, $ l $ не бесплатно.

Для этого конкретного языка для $ s $ any $ a^k $ (с $ k≥p $ и $ k $ является основным номером). Затем насосная лемма дает вам $ uvxyz $ с $ | vy | ≥1 $. Не опровергайте контекстную плотность, вам нужно найти $ n $ так, чтобы $ | uv^nxy^nz | $ не является основным номером.

$$ | uv^nxy^nz | = | s |+(n-1) | vy | = k+(n-1) | vy | $$

И тогда $ n = k+1 $ сделает: $ k+k | vy | = k (1+ | vy |) $ не является Prime, так что $ uv^nxy^nz not in l $. Насосная лемма не может быть применена, так что $ l $ не бесплатна контекста.

Вторым примером является язык $ {ww mid w in {a, b }^{ ast} } $. Мы (конечно) должны выбрать строку и показать, что нет никакого возможного способа, которым ее можно разбить на эти пять частей, и каждая производная нагретая строка остается на языке.

Строка $ s = a^{p} b^{p} a^{p} b^{p} $ является подходящим выбором для этого доказательства. Теперь нам просто нужно посмотреть, где могут быть $ V $ и $ y $. Ключевые детали заключаются в том, что $ V $ или $ y $ должны иметь что -то в нем (возможно, оба), и что как $ V $, так и $ y $ (и $ x $) содержатся в подстроении длины $ p $ - поэтому Они не могут быть слишком далеко друг от друга.

Эта строка имеет ряд возможностей для того, где может быть $ V $ и $ y $, но оказывается, что некоторые из случаев на самом деле выглядят довольно похожими.

  1. $ vy in^{ ast} $ или $ vy in b^{ ast} $. Таким образом, они оба содержатся в одном из разделов контингтоносных $ A $ S или $ B $ S. Это относительно простой случай спорить, так как это не имеет значения, в чем они находятся. Предположим, что $ | vy | = k leq p $.
    • Если они в первом разделе $ a $ s, то когда мы накачаем, первая половина новой строки - $ a^{p+k} b^{pk/2} $, а второе - $ b ^{k/2} a^{p} b^{p} $. Очевидно, это не из формы $ ww $.
    • Аргумент для любого из трех других разделов работает почти одинаково, именно там, где в индексах заканчивается $ K $ и $ K/2 $.
  2. $ vxy $ straddles два из разделов. В этом случае накачан вниз твой друг. Опять же, есть несколько мест, где это может произойти (3, если быть точным), но я просто сделаю один иллюстративный, а остальное должно быть легко выяснить оттуда.
    • Предположим, что $ vxy $ ограничивает границу между первым разделом $ A $ и первым разделом $ b $. Пусть $ vy = a^{k_ {1}} b^{k_ {2}} $ (не имеет значения точно, где $ a $ s и $ b $ s в $ v $ и $ y $, но Мы знаем, что они в порядке). Затем, когда мы перекачиваемся (то есть в случае $ i = 0 $), мы получаем новую строку $ s '= a^{p-k_ {1}} b^{p-k_ {2}} a^{p} b^{p} $, но тогда, если $ s '$ можно разделить на $ ww $, средняя точка должна быть где-то во втором разделе $ a $, поэтому первая половина-$ a^{p-k_ {1} } b^{p-k_ {2}} a^{(k_ {1}+k_ {2})/2} $, а вторая половина-$ a^{p- (k_ {1}+k_ {2 })/2} b^{p} $. Очевидно, что это не та же строка, поэтому мы не можем поместить там $ V $ и $ y $.

Остальные случаи должны быть довольно прозрачными оттуда - они одни и те же идеи, просто размещают $ V $ и $ y $ в других 3 местах в первую очередь и 2 места во втором случае. Однако во всех случаях вы можете накачать его таким образом, чтобы заказ явно испортился, когда вы разделите строку пополам.

Другие советы

Лемма Огдена

Лемма (Огден). Пусть $ l $ будет беспроблемным языком. Тогда есть постоянная $ n $, так что за каждую $ z in l $ и любой способ маркировка $ N $ или более позиций (символов) $ z $ как «выдающиеся позиции», тогда $ z $ можно записать как $ z = uvwxy $, так что, что

  1. $ vx $ имеет хотя бы одну выдающуюся позицию.
  2. $ vwx $ имеет не более выдающиеся должности в $ $.
  3. Для всех $ i geq 0 $, $ uv^iwx^iy in l $.

Пример. Пусть $ l = {a^ib^jc^k: i neq j, j neq k, i neq k } $. Предположим, что $ l $ не является контекстом, и пусть $ n $ будет постоянной, данной Леммой Огдена. Пусть $ z = a^nb^{n+n!} C^{n+2n!} $ (Что принадлежит $ l $), и предположим, что мы отметка в качестве выдающегося все позиции символа $ a $ (то есть первые позиции $ $ z $). Пусть $ z = uvwxy $ будет разложением $ z $, удовлетворяющего условиям от леммы Огдена.

  • Если $ v $ или $ x $ содержат разные символы, то $ uv^2wx^2y notin l $, потому что в неправильном порядке будут символы.
  • По крайней мере, один из $ V $ и $ x $ должен содержать только символы $ A $, потому что только $ A $ были выделены. Таким образом, если $ x in l (b^*) $ или $ x in l (c^*) $, то $ v in l (a^+) $. Пусть $ P = | V | $. Тогда $ 1 leq p leq n $, что означает, что $ p $ делит $ n! $. Пусть $ q = n!/P $. Тогда $ z '= uv^{2q+1} wx^{2q+1} y $ должен принадлежать $ l $. Однако $ v^{2q+1} = a^{2pq+p} = a^{2n!+P} $. Поскольку $ uwy $ имеет ровно $ np $ symbols $ a $, тогда $ Z '$ имеет 2N!+N $ Symbols $ A $. Но у как $ V $, так и $ x $ нет $ C $ 'S, так что $ Z' $ также имеет 2N!+N $ Symbols $ C $, что означает $ Z ' notin l $, и это противоречит Лемма Огдена. Подобное противоречие происходит, если $ x in l (a^+) $ или $ x in l (c^*) $. Мы заключаем, что $ l $ не является контекстом.

Упражнение. Используя лемму Огдена, покажите, что $ l = {a^ib^jc^kd^{ ell}: i = 0 text {или} j = k = ell } $ не является контекстным.

Перекачивая лемму

Это особый случай леммы Огдена, в которой различаются все позиции.

Лемма. Пусть $ l $ будет беспроблемным языком. Тогда существует постоянная $ n $, так что за каждую $ z in l $, $ z $ можно писать как $ z = uvwxy $, так что, что

  1. $ | vx |> 0 $.
  2. $ | vwx | leq n $.
  3. Для всех $ i geq 0 $, $ uv^iwx^iy in l $.

Теорема Париха

Это даже более техническое, чем лемма Огдена.

Определение. Пусть $ sigma = {a_1, ldots, a_n } $. Мы определяем $ psi _ { sigma}: sigma^* to mathbb {n}^n $ by $$ psi _ { sigma} (w) = (m_1, ldots, m_n), $$, где $ $ m_i $ - это количество выступлений $ a_i $ в $ w $.

Определение. Подмножество $ s $ $ mathbb {n}^n $ называется линейный Если это можно записать: $$ s = { mathbf {u_0} + sum_ {1 le i le k} a_i mathbf {u_i}: text {для некоторого набора $ mathbf {u_i} В mathbb {n}^n $ и $ a_i in mathbb {n} $} } $$

Определение. Подмножество $ s $ $ mathbb {n}^n $ называется полулинейный Если это союз конечной коллекции линейных наборов.

Теорема (Парих). Пусть $ l $ будет языком более $ sigma $. Если $ l $-это Context-Free, то $$ psi _ { sigma} [l] = { psi _ { sigma} (w): w in l } $$ является полулинейным.

Упражнение. Используя теорему Париха, покажите, что $ l = {0^m1^n: m> n text {или} (m text {is prime и} m leq n) } $ не является контекстным.

Упражнение. Используя теорему Parikh, покажите, что любой контекстный язык над унарным алфавитом также является регулярным.

Свойства закрытия

После небольшой коллекции языков без контекста вы часто можете использовать Свойства закрытия $ mathrm {cfl} $

Предположим, что $ l in mathrm {cfl} $. Затем, по свойству закрытия x (вместе с Y), $ l ' in mathrm {cfl} $. Это противоречит $ l ' notin mathrm {cfl} $, которую мы знаем, поэтому $ l notin mathrm {cfl} $.

Это часто бывает короче (и часто менее подверженным ошибкам), чем использование одного из других результатов, которые используют менее предварительные знания. Это также общая концепция, которую можно применять все виды класса объектов.

Пример 1: Пересечение с обычными языками

Мы отмечаем $ mathcal l (e) $ обычный язык, указанный любым регулярным выражением $ e $.

Пусть $ l = {w mid W in {a, b, c }^*, | w | _a = | w | _b = | w | _c } $. В качестве

$ qquad displaystyle l cap mathcal {l} (a^*b^*c^*) = {a^nb^nc^n mid n in mathbb {n} } notin mathrm {Cfl} $

и $ mathrm {cfl} $ закрыт на пересечении с обычными языками, $ l notin mathrm {cfl} $.

Пример 2: (Обратный) гомоморфизм

Пусть $ l = {(ab)^{2n} c^md^{2n-m} (aba)^{n} mid m, n in mathbb {n} } $. С гомоморфизмом

$ qquad displaystyle phi (x) = begin {case} a & x = a varepsilon & x = b b & x = c lor x = d end {case} $

У нас есть $ phi (l) = {a^{2n} b^{2n} a^{2n} mid n in mathbb {n} }. $

Теперь с

$ qquad displaystyle psi (x) = begin {case} aa & x = a lor x = c bb & x = b end {case} Quad text {и} Quad L_1 = {x ^nb^ny^n mid x, y in {a, c } wedge n in mathbb {n} }, $

Мы получаем $ l_1 = psi^{-1} ( phi (l))) $.

Наконец, пересечение $ l_1 $ с обычным языком $ l_2 = mathcal l (a^*b^*c^*) $ Мы получаем язык $ l_3 = {a^nb^nc^n mid n in in mathbb {n} } $.

В общей сложности у нас есть $ l_3 = l_2 cap psi^{-1} ( phi (l)) $.

Теперь предположим, что $ l $ была свободной от контекста. Затем, поскольку $ mathrm {cfl} $ закрыт против гомоморфизма, обратного гомоморфизма и пересечения с регулярными наборами, $ l_3 $ также не имеет контекста. Но мы знать (С помощью накачки леммы, если необходимо), что $ l_3 $ не является контекстным, так что это противоречие; Мы показали, что $ l notin mathrm {cfl} $.

Обмен лемма

А Обмен лемма 1] предлагает необходимое условие для контекстной фризоны, которое даже сильнее, чем Лемма Огдена. Анкет Например, его можно использовать, чтобы показать, что

$ qquad {xyyz mid x, y, z in {a, b, c }^+} notin mathrm {cfl} $

который противостоит многим другим методам. Это лемма:

Пусть $ l in mathrm {cfl} $. Тогда есть постоянная $ c_l $, так что для любого целого числа $ n geq 2 $ любой набор $ q_n subteq l_n = l cap sigma^n $ и любое целое число $ m $ с $ n geq m geq 2 $ Есть $ k geq frac {| q_n |} {c_l n^2} $ Strings $ z_i in q_n $ с

  1. $ z_i = w_ix_iy_i $ для $ i = 1, dots, k $,
  2. $ | W_1 | = | W_2 | = dots = | w_k | $,
  3. $ | y_1 | = | y_2 | = dots = | y_k | $,
  4. $ m geq | x_1 | = | X_2 | = dots = | x_k | > frac {m} {2} $ и
  5. $ w_ix_jy_i in l_n $ для всех $ (i, j) in [1..k]^2 $.

Применение его означает найти $ N, M $ и $ Q_N $, что 1.-4. Держите, но 5. нарушается. Пример приложения, приведенный в исходной статье, очень многословный и поэтому остается здесь.

В настоящее время у меня нет свободно доступной ссылки, и приведенная выше формулировка взята из предварительной обработки [1] с 1981 года. Я ценю помощь в отслеживании лучших ссылок. Похоже, что такое же свойство было обнаружено недавно [2].

Другие необходимые условия

Boonyavatana и Slutzki [3] обследовали несколько условий, аналогичных накачанной и обменной леммой.

  1. «Обмена леммы» для языков без контекста. У. Огден, Р.Дж. Росс и К. Винклманн (1985)
  2. Обмен леммы на регулярные и беспроблемные языки Т. Ямаками (2008)
  3. Обменные или насосные (DI) леммы для языков без контекста Р. Бонейватана и Г. Струцки (1988)

Нет общего метода, так как набор, не содержащий контекста, не имеет языка, не является полуветным (AKARE). Если бы был общий метод, мы могли бы использовать его для полудецида этого набора.

Ситуация еще хуже, поскольку учитывая два КЛЛ, невозможно решить, является ли их пересечение также КЛЛ.

Ссылка: Hopcroft и Ullman, «Введение в теорию автоматов, языки и вычисления», 1979.

Более сильная версия состояния Огдена (ОК) это

Состояние Бадера-Мура (BMC)

Язык $ l subteq sigma^*$ удовлетворяет BMC, если существует постоянная $ n $ так, что если $ z in l $ и мы помечаем в нем «выдающиеся» позиции $ d (z) $ и $ e (z ) $ "исключенные" позиции, с $ d (z)> n^{e (z) +1} $, тогда мы можем написать $ z = uvwxy $ так:

  1. $ d (vx) geq 1 $ и $ e (vx) = 0 $
  2. $ d (vwx) leq n^{e (vwx) +1} $ и
  3. за каждый $ i geq 0 $, $ uv^iwx^iy $ находится в $ l $.

Мы говорим, что язык $ l в BMC ( Sigma) $ Если $ l $ удовлетворяет условию Бадера-Мура.

У нас есть $ cfl ( sigma) subsmet bmc ( sigma) submet oc ( sigma) $, поэтому BMC строго сильнее OC.

Ссылка: Bader, C., Moura, A., обобщение леммы Огдена. Jacm 29, нет. 2, (1982), 404–407

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top