Дық тілі – компьютер ғылымындағы тепе-тең жақшалар тізбегі. Математика, лингвистикада қолданылады. Дық сөздер мен тілі Walther von Dyck есімімен аталған.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Қашарлардың теңгерілген тізбектерінен тұратын тіл
Language consisting of balanced strings of brackets
Компьютер ғылымы, математика және тіл білімінің формальді тілдер теориясында, Дик сөзі – қашарлардың теңгерілген тізбегі. Дик сөздерінің жиынтығы Дик тілін құрайды. Ең қарапайымы, D1, тек екі сәйкес келетін қашарды қолданады, мысалы, ( және ). Дик сөздері мен тілі математик Вальтер фон Диктің құрметіне аталған. Олар арифметикалық немесе алгебралық өрнектер сияқты, қашарлардың дұрыс ұялатылған тізбегі болуы керек өрнектерді талдауда қолданылады.
In the theory of formal languages of computer science, mathematics, and linguistics, a Dyck word is a balanced string of brackets. The set of Dyck words forms a Dyck language. The simplest, D1, uses just two matching brackets, e. g. ( and ). Dyck words and language are named after the mathematician Walther von Dyck. They have applications in the parsing of expressions that must have a correctly nested sequence of brackets, such as arithmetic or algebraic expressions.
Қасиеттері
Дик тілі конкатенция операциясы бойынша жабық. Конкатенция бойынша алгебралық моноид ретінде қарастыра отырып, моноид құрылымының quotient-ке ауысатынын көреміз, нәтижесінде Дик тілінің синтаксистік моноиды пайда болады. Сынып деп белгіленеді. Дик тілінің синтаксистік моноиды коммутативті емес: егер және онда . Жоғарыда көрсетілген белгімен, бірақ немесе екеуі де -де инверттендірілмейді. Дик тілінің синтаксистік моноиды жоғарыда сипатталған және қасиеттеріне сәйкес бициклдік жартылай топқа изоморфты. Чомский-Шутценбергердің бейнелеу теоремасы бойынша, кез келген контекстсіз тіл – бір немесе бірнеше түрдегі жақша жұптарындағы Дик тілімен кейбір реттелі тілдің қиылысының гомоморфты бейнесі болып табылады. Екі түрлі жақшалы Дик тілі күрделілік класында танылуы мүмкін. Дәл n жұп жақшасы және k ішкі жұптары бар (яғни, ) Дик сөздерінің саны – Нараяна саны. Дәл n жұп жақшасы бар Дик сөздердің саны – n-ші Каталон саны. n жұп жақшасы бар Дик тілі, алдыңғы тармақта анықталғандай, n жұп жақшасы бар және k ішкі жұптары бар Дик тілдерінің барлық мүмкін k бойынша бірігуіне тең екенін ескеріңіз. k 0-ден n-ге дейін өзгере алатындықтан, біз келесі теңдікті аламыз, ол шындығында дұрыс:
The Dyck language is closed under the operation of concatenation. By treating as an algebraic monoid under concatenation we see that the monoid structure transfers onto the quotient , resulting in the syntactic monoid of the Dyck language. The class will be denoted The syntactic monoid of the Dyck language is not commutative: if and then With the notation above, but neither nor are invertible in The syntactic monoid of the Dyck language is isomorphic to the bicyclic semigroup by virtue of the properties of and described above. By the Chomsky–Schützenberger representation theorem, any context free language is a homomorphic image of the intersection of some regular language with a Dyck language on one or more kinds of bracket pairs. The Dyck language with two distinct types of brackets can be recognized in the complexity class The number of distinct Dyck words with exactly n pairs of parentheses and k innermost pairs (viz. the substring ) is the Narayana number The number of distinct Dyck words with exactly n pairs of parentheses is the n th Catalan number Notice that the Dyck language of words with n parentheses pairs is equal to the union, over all possible k, of the Dyck languages of words of n parentheses pairs with k innermost pairs, as defined in the previous point. Since k can range from 0 to n, we obtain the following equality, which indeed holds:
Жалпылау
Dyck тілінің бірнеше шектеуіштермен нұсқалары бар, мысалы, "(", ")", "[", және "]" әріптерінен құралған D2. Мұндай тілдің сөздері – барлық шектеуіштер бойынша дұрыс жабын салынған сөздер, яғни сөзді солдан оңға қарай оқығанда, әр ашық шектеуішті стекке қоюға болады, ал жабық шектеуіш кездескенде, стек жоғарғы жағынан сәйкес ашық шектеуішті алып тастау керек. (Жоғарыдағы сану алгоритмі осы жағдайға қолданылмайды).
There exist variants of the Dyck language with multiple delimiters, e. g., D2 on the alphabet "(", ")", "[", and "]". The words of such a language are the ones which are well parenthesized for all delimiters, i. e., one can read the word from left to right, push every opening delimiter on the stack, and whenever we reach a closing delimiter then we must be able to pop the matching opening delimiter from the top of the stack. (The counting algorithm above does not generalise).