Limbaj recursiv - Recursive language

În matematică , logică și informatică , un limbaj formal (un set de secvențe finite de simboluri luate dintr-un alfabet fix ) se numește recursiv dacă este un subset recursiv al setului tuturor secvențelor finite posibile peste alfabetul limbajului. În mod echivalent, un limbaj formal este recursiv dacă există o mașină Turing totală (o mașină Turing care se oprește pentru fiecare intrare dată) care, atunci când este dată o secvență finită de simboluri ca intrare, o acceptă dacă aparține limbii și o respinge altfel. Limbajele recursive sunt, de asemenea, numite decidabile .

Conceptul de decizie poate fi extins la alte modele de calcul . De exemplu, se poate vorbi de limbi care se pot decide pe o mașină de Turing nedeterministă . Prin urmare, ori de câte ori este posibil , o ambiguitate, sinonimul folosit pentru „limbaj recursiv“ este Turing-decidabile limbă , mai degrabă decât pur și simplu decidabile .

Clasa tuturor limbajelor recursive se numește adesea R , deși acest nume este folosit și pentru clasa RP .

Acest tip de limbaj nu a fost definit în ierarhia Chomsky din ( Chomsky 1959 ). Toate limbajele recursive sunt, de asemenea, recursiv enumerabile . Toate regulate , context liber și sensibile la context de limbi sunt recursiv.

Definiții

Există două definiții majore echivalente pentru conceptul de limbaj recursiv:

1. Un limbaj formal recursiv este un recursiv subset din setul de toate cuvintele posibile asupra alfabetului al limbii .
2. Un limbaj recursiv este un limbaj formal pentru care există o mașină Turing care, atunci când este prezentată cu orice șir de intrare finit , oprește și acceptă dacă șirul este în limbă și oprește și respinge altfel. Mașina Turing se oprește întotdeauna: este cunoscută ca un decider și se spune că decide limbajul recursiv.

Prin a doua definiție, orice problemă de decizie poate fi demonstrată a fi decisă prin expunerea unui algoritm pentru aceasta care se termină pe toate intrările. O problemă indecidabilă este o problemă care nu poate fi decisă.

Exemple

După cum sa menționat mai sus, fiecare limbaj sensibil la context este recursiv. Astfel, un exemplu simplu de limbaj recursiv este mulțimea L = {abc, aabbcc, aaabbbccc, ...} ; mai formal, setul

${\ displaystyle L = \ {\, w \ in \ {a, b, c \} ^ {*} \ mid w = a ^ {n} b ^ {n} c ^ {n} {\ mbox {pentru unele }} n \ geq 1 \, \}}$

este sensibil la context și, prin urmare, recursiv.

Exemplele de limbaje care pot fi luate în considerare, care nu sunt sensibile la context, sunt mai greu de descris. Pentru un astfel de exemplu, este necesară o anumită familiaritate cu logica matematică : aritmetica Presburger este teoria de ordinul întâi a numerelor naturale cu adunare (dar fără multiplicare). În timp ce setul de formule bine formate din aritmetica Presburger nu conține contexte, fiecare mașinărie Turing deterministă care acceptă setul de afirmații adevărate în aritmetica Presburger are cel mai rău timp de rulare de cel puțin , pentru o constantă c > 0 ( Fischer & Rabin 1974 ). Aici, n reprezintă lungimea formulei date. Deoarece fiecare limbaj sensibil la context poate fi acceptat de un automat liniar delimitat și un astfel de automat poate fi simulat de o mașină Turing deterministă cu cel mai rău caz de funcționare cel mult pentru o constantă c , setul de formule valide în aritmetica Presburger nu este sensibil la context. Pe partea pozitivă, se știe că există o mașină Turing deterministă care funcționează în timp cel mult triplu exponențial în n care decide setul de formule adevărate în aritmetica Presburger ( Oppen 1978 ). Astfel, acesta este un exemplu de limbaj care poate fi decis, dar nu sensibil la context. ${\ displaystyle 2 ^ {2 ^ {cn}}}$${\ displaystyle c ^ {n}}$

Proprietăți de închidere

Limbajele recursive sunt închise în următoarele operațiuni. Adică, dacă L și P sunt două limbi recursive, atunci și următoarele limbi sunt recursive:

• Kleene stele ${\ displaystyle L ^ {*}}$
• Imaginea φ (L) sub un omomorfism e-free φ
• Concatenarea ${\ displaystyle L \ circ P}$
• Uniunea ${\ displaystyle L \ cup P}$
• Intersecția ${\ displaystyle L \ cap P}$
• Complementul ${\ displaystyle L}$
• Diferența stabilită ${\ displaystyle LP}$

Ultima proprietate rezultă din faptul că diferența setată poate fi exprimată în termeni de intersecție și complement.

Vezi si

• Limbaj recursiv enumerabil
• Recursivitate

Referințe

• Michael Sipser (1997). „Decidabilitate” . Introducere în teoria calculației . Editura PWS. pp.  151–170 . ISBN 978-0-534-94728-6.
• Chomsky, Noam (1959). „Despre anumite proprietăți formale ale gramaticilor” . Informații și control . 2 (2): 137–167. doi : 10.1016 / S0019-9958 (59) 90362-6 .
• Fischer, Michael J .; Rabin, Michael O. (1974). „Complexitatea super-exponențială a aritmeticii Presburger” . Lucrările Simpozionului SIAM-AMS în matematică aplicată . 7 : 27–41.
• Oppen, Derek C. (1978). „A 2 ^{2 2 pn} Upper Bound on the Complexity of Presburger Arithmetic” . J. Comput. Syst. Știință . 16 (3): 323–332. doi : 10.1016 / 0022-0000 (78) 90021-1 .