Rekursivt uppräknat språk

Inom matematik, logik och datavetenskap är ett rekursivt uppräknat språk en typ av formellt språk, även känt som delvis avgörbart , eller Turing-igenkännbart . I Chomsky-hierarkin är det känt som ett språk av typ 0. Klassen av alla rekursivt uppräknade språk kallas RE.

Definitioner

Det finns tre huvudsakliga ekvivalenta definitioner av begreppet ett rekursivt uppräknat språk.

1. Ett rekursivt uppräknat formellt språk är en rekursivt uppräknad delmängd av uppsättningen av alla möjliga ord över språkalfabetet .
2. Ett rekursivt uppräknat språk är ett formellt språk för vilket det finns en Turing-maskin (eller annan beräkningsbar funktion ) som räknar upp alla giltiga strängar i språket. Observera att om språket är oändligt, så kan man välja en uppräkningsalgoritm som undviker upprepningar, eftersom man för en sträng numrerad n kan kontrollera om den "redan" har returnerats till ett nummer mindre än n . Om det fanns, använd sedan utgångsnummer n+1 istället (rekursivt), och kontrollera igen om den är "ny".
3. Ett rekursivt uppräknat språk är ett formellt språk för vilket det finns en Turing-maskin (eller annan beräkningsbar funktion ) som stoppar och accepterar vilken inmatningssträng som helst från språket, men stoppar och avvisar eller inte stoppar alls för någon inmatningssträng som inte kommer från språket . Rekursiva språk kräver att Turing-maskinen stannar ändå.

Alla vanliga, sammanhangsfria, sammanhangskänsliga och rekursiva språk är rekursivt uppräknade.

Posts sats visar att RE, tillsammans med ytterligare co-RE, motsvarar den första nivån i den aritmetiska hierarkin .

Stängningsegenskaper

Rekursivt uppräknade språk stängs under följande operationer. Låt L och P  vara två rekursivt uppräknbara språk, då är följande språk också rekursivt uppräknbara:

• Kleene stjärna från L
• sammanlänkning från L och P
• En förening
• genomskärning

Observera att rekursivt uppräknade språk inte stängs under skillnad eller komplement. Den inställda skillnaden L \ P kan vara rekursivt uppräknad eller inte. Om L är rekursivt uppräknbart, så är komplementet till L rekursivt uppräkbart om och endast om L också är rekursivt.

Litteratur

Gladkiy A. V. Formella grammatiker och språk. - M . : "Nauka", 1973. - 368 sid.