[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/conjunctive-grammar-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/conjunctive-grammar-wikipedia\/","headline":"Conjunctive grammar – Wikipedia","name":"Conjunctive grammar – Wikipedia","description":"before-content-x4 Conjunctive grammars are a class of formal grammars studied in formal language theory. They extend the basic type of","datePublished":"2014-01-27","dateModified":"2014-01-27","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/cd810e53c1408c38cc766bc14e7ce26a?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/cd810e53c1408c38cc766bc14e7ce26a?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/25629e1af201710e0c5521c7c0f188d9d8acd684","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/25629e1af201710e0c5521c7c0f188d9d8acd684","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/conjunctive-grammar-wikipedia\/","wordCount":6381,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Conjunctive grammars are a class of formal grammarsstudied in formal language theory.They extend the basic type of grammars,the context-free grammars,with a conjunction operation.Besides explicit conjunction,conjunctive grammars allow implicit disjunctionrepresented by multiple rules for a single nonterminal symbol,which is the only logical connective expressible in context-free grammars.Conjunction can be used, in particular,to specify intersection of languages.A further extension of conjunctive grammarsknown as Boolean grammarsadditionally allows explicit negation.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4The rules of a conjunctive grammar are of the formA\u2192\u03b11&\u2026&\u03b1m{displaystyle Ato alpha _{1}And ldots And alpha _{m}}where        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4A{displaystyle A} is a nonterminal and\u03b11{displaystyle alpha _{1}}, …, \u03b1m{displaystyle alpha _{m}}are strings formed of symbols in \u03a3{displaystyle Sigma } and        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4V{displaystyle V} (finite sets of terminal and nonterminal symbols respectively).Informally, such a rule asserts thatevery string w{displaystyle w} over \u03a3{displaystyle Sigma }that satisfies each of the syntactical conditions representedby \u03b11{displaystyle alpha _{1}}, …, \u03b1m{displaystyle alpha _{m}}therefore satisfies the condition defined by A{displaystyle A}.Table of ContentsFormal definition[edit]Definition by derivation[edit]Example[edit]Parsing algorithms[edit]Theoretical properties[edit]Synchronized alternating pushdown automata[edit]References[edit]External links[edit]Formal definition[edit]A conjunctive grammar G{displaystyle G} is defined by the 4-tuple G=(V,\u03a3,R,S){displaystyle G=(V,Sigma ,R,S)} whereV is a finite set; each element v\u2208V{displaystyle vin V} is called a nonterminal symbol or a variable. Each variable represents a different type of phrase or clause in the sentence. Variables are also sometimes called syntactic categories.\u03a3 is a finite set of terminals, disjoint from V, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar G.R is a finite set of productions, each of the form A\u2192\u03b11&\u2026&\u03b1m{displaystyle Arightarrow alpha _{1}&ldots &alpha _{m}} for some A{displaystyle A} in V{displaystyle V} and \u03b1i\u2208(V\u222a\u03a3)\u2217{displaystyle alpha _{i}in (Vcup Sigma )^{*}}. The members of R are called the rules or productions of the grammar.S is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of V.It is common to list all right-hand sides for the same left-hand side on the same line, using | (the pipe symbol) to separate them. Rules A\u2192\u03b11&\u2026&\u03b1m{displaystyle Arightarrow alpha _{1}&ldots &alpha _{m}} and A\u2192\u03b21&\u2026&\u03b2n{displaystyle Arightarrow beta _{1}&ldots &beta _{n}} can hence be written as A\u2192\u03b11&\u2026&\u03b1m\u00a0|\u00a0\u03b21&\u2026&\u03b2n{displaystyle Arightarrow alpha _{1}&ldots &alpha _{m} | beta _{1}&ldots &beta _{n}}.Two equivalent formal definitionsof the language specified by a conjunctive grammar exist.One definition is based upon representing the grammaras a system of language equations with union, intersection and concatenationand considering its least solution.The other definition generalizesChomsky’s generative definition of the context-free grammarsusing rewriting of terms over conjunction and concatenation.Definition by derivation[edit]For any strings u,v\u2208(V\u222a\u03a3\u222a{\u201c(\u201d,\u201c&\u201d,\u201c)\u201d})\u2217{displaystyle u,vin (Vcup Sigma cup {{text{\u201c(\u201d}},{text{\u201c}}&{text{\u201d}},{text{\u201c)\u201d}}})^{*}}, we say u directly yields v, written as u\u21d2v{displaystyle uRightarrow v,}, ifFor any string w\u2208\u03a3\u2217,{displaystyle win Sigma ^{*},} we say G generates w, written as S\u00a0\u21d2\u2217\u00a0w{displaystyle S {stackrel {*}{Rightarrow }} w}, if \u2203k\u22651\u2203u1,\u22ef,uk\u2208(V\u222a\u03a3\u222a{\u201c(\u201d,\u201c&\u201d,\u201c)\u201d})\u2217{displaystyle exists kgeq 1,exists ,u_{1},cdots ,u_{k}in (Vcup Sigma cup {{text{\u201c(\u201d}},{text{\u201c}}&{text{\u201d}},{text{\u201c)\u201d}}})^{*}} such that S=u1\u21d2u2\u21d2\u22ef\u21d2uk=w{displaystyle S=,u_{1}Rightarrow u_{2}Rightarrow cdots Rightarrow u_{k},=w}.The language of a grammar G=(V,\u03a3,R,S){displaystyle G=(V,Sigma ,R,S)} is the set of all strings it generates.Example[edit]The grammar G=({S,A,B,C,D},{a,b,c},R,S){displaystyle G=({S,A,B,C,D},{a,b,c},R,S)}, with productionsS\u2192AB&DC{displaystyle Srightarrow AB&DC},A\u2192aA\u00a0|\u00a0\u03f5{displaystyle Arightarrow aA | epsilon },B\u2192bBc\u00a0|\u00a0\u03f5{displaystyle Brightarrow bBc | epsilon },C\u2192cC\u00a0|\u00a0\u03f5{displaystyle Crightarrow cC | epsilon },D\u2192aDb\u00a0|\u00a0\u03f5{displaystyle Drightarrow aDb | epsilon },is conjunctive. A typical derivation isS\u21d2(AB&DC)\u21d2(aAB&DC)\u21d2(aB&DC)\u21d2(abBc&DC)\u21d2(abc&DC)\u21d2(abc&aDbC)\u21d2(abc&abC)\u21d2(abc&abcC)\u21d2(abc&abc)\u21d2abc{displaystyle SRightarrow (AB&DC)Rightarrow (aAB&DC)Rightarrow (aB&DC)Rightarrow (abBc&DC)Rightarrow (abc&DC)Rightarrow (abc&aDbC)Rightarrow (abc&abC)Rightarrow (abc&abcC)Rightarrow (abc&abc)Rightarrow abc}It can be shown that L(G)={anbncn:n\u22650}{displaystyle L(G)={a^{n}b^{n}c^{n}:ngeq 0}}. The language is not context-free, proved by the pumping lemma for context-free languages.Parsing algorithms[edit]Though the expressive power of conjunctive grammarsis greater than those of context-free grammars,conjunctive grammars retain some of the latter.Most importantly, there are generalizations of the main context-free parsing algorithms,including the linear-time recursive descent,the cubic-time generalized LR,the cubic-time Cocke-Kasami-Younger,as well as Valiant’s algorithm running as fast as matrix multiplication.Theoretical properties[edit]A property that is undecidable already for context-free languages or finite intersections of them, must be undecidable also for conjunctive grammars; these include:emptiness, finiteness, regularity, context-freeness,[n 1] inclusion and equivalence.[n 2]The family of conjunctive languages is closed under union, intersection, concatenation and Kleene star, but not under string homomorphism, prefix, suffix, and substring.Closure under complement and under \u03b5-free string homomorphism are still open problems (as of 2001).[1]:\u200a533\u200aThe expressive power of grammars over a one-letter alphabet has been researched.[citation needed]This work provided a basisfor the study of language equations of a more general form.Synchronized alternating pushdown automata[edit]Aizikowitz and Kaminski[2] introduced a new class of pushdown automata (PDA) called synchronized alternating pushdown automata (SAPDA). They proved it to be equivalent to conjunctive grammars in the same way as nondeterministic PDAs are equivalent to context-free grammars.^ Given a conjunctive grammar, is its generated language empty \/ finite \/ regular \/ context-free?^ Given two conjunctive grammars, is the first’s generated language a subset of \/ equal to the second’s?References[edit]^ Alexander Okhotin (2001). “Conjunctive Grammars” (PDF). Journal of Automata, Languages and Combinatorics. 6 (4): 519\u2013535.^ Aizikowitz, Tamar; Kaminski, Michael (2011). “LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata”. Computer Science \u2013 Theory and Applications. Lecture Notes in Computer Science. Vol.\u00a06651. pp.\u00a0345\u2013358. doi:10.1007\/978-3-642-20712-9_27. ISBN\u00a0978-3-642-20711-2. ISSN\u00a00302-9743.External links[edit]     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/conjunctive-grammar-wikipedia\/#breadcrumbitem","name":"Conjunctive grammar – Wikipedia"}}]}]