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.
Det finns tre huvudsakliga ekvivalenta definitioner av begreppet ett rekursivt uppräknat språk.
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 .
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:
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.
Gladkiy A. V. Formella grammatiker och språk. - M . : "Nauka", 1973. - 368 sid.
Formella språk och formella grammatiker | |
---|---|
Allmänna begrepp | |
Typ 0 | |
Typ 1 |
|
Typ 2 | |
Typ 3 |
|
analysera |