Контексттік сезімтал тілдер және формальды грамматикалар
Context-sensitive language
Контексті сезімтал тілдер: формальды тілдер теориясы, Chomsky иерархиясы, шектеусіз автоматтар. Лин. белгілі автоматтармен байланысы. SEO үшін оптимизацияланған.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Формалды тіл теориясында контекстке тәуелді тіл – контекстке тәуелді грамматикамен (және теңдесінше, келісімді қысқармайтын грамматикамен) анықталатын тіл. Контекстке тәуелділік Чомскидің формальды тілдер иерархиясында 1-тип деп белгіленеді.
In formal language theory, a context sensitive language is a language that can be defined by a context sensitive grammar (and equivalently by a noncontracting grammar). Context sensitive is known as type 1 in the Chomsky hierarchy of formal languages.
Есептеу қасиеттері
Есептеу тұрғысынан, контекстке сезімтал тіл сызықтық шектелген нондетерминистік Тьюринг машинасына тең, оны сызықтық шектелген автомат деп те атайды. Яғни, бұл кірістің көлемі және машинаға қатысты тұрақты болған жағдайда, тек ұяшықтан тұратын таспасы бар детерминистік емес Тьюринг машинасы. Бұл, мұндай машинамен шешілетін кез келген формальды тіл контекстке сезімтал тіл болады, ал кез келген контекстке сезімтал тіл осындай машинамен шешіле алады дегенді білдіреді. Бұл тілдер жиынтығы NLINSPACE немесе NSPACE(O(n)) деп те белгілі, себебі оларды нондетерминистік Тьюринг машинасымен сызықтық кеңістікті пайдаланып қабылдауға болады. LINSPACE (немесе DSPACE(O(n))) класы да осылай анықталады, бірақ детерминистік Тьюринг машинасы қолданылады. Әрине, LINSPACE – NLINSPACE-тің ішкі жиыны, бірақ LINSPACE = NLINSPACE екендігі әлі белгісіз.
Computationally, a context sensitive language is equivalent to a linear bounded nondeterministic Turing machine, also called a linear bounded automaton. That is a non deterministic Turing machine with a tape of only cells, where is the size of the input and is a constant associated with the machine. This means that every formal language that can be decided by such a machine is a context sensitive language, and every context sensitive language can be decided by such a machine. This set of languages is also known as NLINSPACE or NSPACE(O(n)), because they can be accepted using linear space on a non deterministic Turing machine. The class LINSPACE (or DSPACE(O(n))) is defined the same, except using a deterministic Turing machine. Clearly LINSPACE is a subset of NLINSPACE, but it is not known whether LINSPACE = NLINSPACE.
Контекстке бейімделген тілдердің қасиеттері
Екі контексті сезімтал тілдің бірігуі, қиылысуы, тізбектелуі контексті сезімтал, сондай-ақ контексті сезімтал тілдің Клейне жұлдызы контексті сезімтал болады. Контексті сезімтал тілдің толықтырғышы өзі контексті сезімтал, бұл нәтиже Иммерман-Селепчени теоремасы деп аталады. Кез келген контексті сезімтал грамматикамен немесе кез келген детерминистік контексті сезімтал грамматикамен анықталған тілдегі тізбектің мүшелігі – PSPACE толық проблемасы болып табылады.
The union, intersection, concatenation of two context sensitive languages is context sensitive, also the Kleene plus of a context sensitive language is context sensitive. The complement of a context sensitive language is itself context sensitive a result known as the Immerman–Szelepcsényi theorem. Membership of a string in a language defined by an arbitrary context sensitive grammar, or by an arbitrary deterministic context sensitive grammar, is a PSPACE complete problem.