Język bezkontekstowy
Z Wikipedii, wolnej encyclopedia
Język bezkontekstowy (ang. context-free language) – język formalny taki, że istnieje niedeterministyczny automat ze stosem decydujący czy dany łańcuch należy do języka. Równoważnie, taki, że istnieje dlań gramatyka bezkontekstowa. W hierarchii Chomsky’ego jest zdefiniowany jako język typu 2.
Rodzina języków regularnych jest podzbiorem zbioru języków bezkontekstowych. Każdy język bezkontekstowy jest językiem kontekstowym.
Języki bezkontekstowe mają ważne znaczenie w informatyce, m.in. w budowie kompilatorów; patrz analiza składniowa.