Лемма алмасу - Interchange lemma

Бұл мақала тым көп сүйенеді сілтемелер дейін бастапқы көздер. Мұны қосу арқылы жақсартыңыз екінші немесе үшінші реттік көздер. (Наурыз 2019) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз)

Теориясында ресми тілдер, алмасу леммасы тілдің болуы үшін қажетті шартты айтады контекстсіз, дәл сол сияқты контекстсіз тілдер үшін лемманы айдау.

Онда әрбір контекстсіз тіл үшін айтылады ${ displaystyle L}$ бар ${ displaystyle c> 0}$ бәріне арналған ${ displaystyle n geq m geq 2}$ ұзындықтың кез-келген коллекциясы үшін ${ displaystyle n}$ сөздер ${ displaystyle R ішкі жиын L}$ бар ${ displaystyle Z = {z_ {1}, ldots, z_ {k} } ішкі жиын R}$ бірге ${ displaystyle k geq | R | / (cn ^ {2})}$және ыдырау ${ displaystyle z_ {i} = w_ {i} x_ {i} y_ {i}}$ әрқайсысы сияқты ${ displaystyle | w_ {i} |}$, ${ displaystyle | x_ {i} |}$, ${ displaystyle | y_ {i} |}$ тәуелді емес ${ displaystyle i}$сонымен қатар, ${ displaystyle m / 2 <| x_ {i} | leq m}$және сөздер ${ displaystyle w_ {i} x_ {j} y_ {i}}$ бар ${ displaystyle L}$ әрқайсысы үшін ${ displaystyle i}$ және ${ displaystyle j}$.

Ауыстыру леммасының алғашқы қолданылуы қайталанатын жолдар жиынтығын (яғни форманың жолдарын) көрсету болды. ${ displaystyle xyyz}$ бірге ${ displaystyle | y |> 0}$) үш немесе одан көп таңбадан тұратын алфавиттің үстінен контекстсіз болмайды

Сондай-ақ қараңыз

• Кәдімгі тілдерге арналған лемманы айдау

Пайдаланылған әдебиеттер

• Уильям Огден, Рокфорд Дж. Росс және Карл Винклманн (1982). «Контекстсіз тілдерге арналған» алмасу леммасы «». Есептеу бойынша SIAM журналы. 14 (2): 410–415. дои:10.1137/0214031.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)