Boolean grammar (original) (raw)
Boolean grammars, introduced by , are a class of formal grammars studied in formal language theory. They extend the basic type of grammars, the context-free grammars, with conjunction and negation operations. Besides these explicit operations, Boolean grammars allow implicit disjunction represented by multiple rules for a single nonterminal symbol, which is the only logical connective expressible in context-free grammars. Conjunction and negation can be used, in particular, to specify intersection and complement of languages. An intermediate class of grammars known as conjunctive grammars allows conjunction and disjunction, but not negation.
| Property | Value |
|---|---|
| dbo:abstract | Boolean grammars, introduced by , are a class of formal grammars studied in formal language theory. They extend the basic type of grammars, the context-free grammars, with conjunction and negation operations. Besides these explicit operations, Boolean grammars allow implicit disjunction represented by multiple rules for a single nonterminal symbol, which is the only logical connective expressible in context-free grammars. Conjunction and negation can be used, in particular, to specify intersection and complement of languages. An intermediate class of grammars known as conjunctive grammars allows conjunction and disjunction, but not negation. The rules of a Boolean grammar are of the form where is a nonterminal, and , ..., , , ..., are strings formed of symbols in and . Informally, such a rule asserts that every string over that satisfies each of the syntactical conditions represented by , ..., and none of the syntactical conditions represented by , ..., therefore satisfies the condition defined by . There exist several formal definitions of the language generated by a Boolean grammar. They have one thing in common: if the grammar is represented as a system of language equations with union, intersection, complementation and concatenation, the languages generated by the grammar must be the solution of this system. The semantics differ in details, some define the languages using language equations, some draw upon ideas from the field of logic programming. However, these nontrivial issues of formal definition are mostly irrelevant for practical considerations, and one can construct grammars according to the given informal semantics. The practical properties of the model are similar to those of conjunctive grammars, while the descriptional capabilities are further improved. In particular, some practically useful properties inherited from context-free grammars, such as efficient parsing algorithms, are retained, see . (en) Las gramáticas booleanas, introducidas por Okhotin, son una clase de gramáticas formales estudiadas en la teoría de lenguajes formales. Esta gramáticas extienden el tipo básico de gramáticas, las gramáticas libres de contexto con operaciones de conjunción y negación. Además de estas operaciones explícitas, las gramáticas booleanas permiten la disyunción implícita representada por múltiples reglas para un solo símbolo no terminal, que es la única conectividad lógica expresable en gramáticas libres de contexto. La conjunción y la negación pueden usarse, en particular, para especificar la intersección y el complemento de los idiomas. Una clase intermedia de gramáticas conocidas como permite la conjunción y la disyunción pero no la negación. Las reglas de una gramática booleana tienen la forma dónde es un no-terminal, y , ..., , , ..., son cadenas formadas de símbolos en y . Informalmente, tal regla afirma que cada cadena sobre que satisface cada una de las condiciones sintácticas representadas por , ..., y ninguna de las condiciones sintácticas representadas por , ..., satisface la condición definida por . Existen varias definiciones formales del lenguaje generado por una gramática booleana. Tienen una cosa en común: si la gramática se representa como un sistema de lenguajes de ecuaciones con uniones, intersecciones, complementos y concatenación, los lenguajes generados por la gramática deben ser la solución de este sistema. La semántica difiere en detalles, algunos definen los lenguajes usando ecuaciones de lenguaje, algunos se basan en ideas del campo de la programación lógica. Sin embargo, estos problemas no triviales de definición formal son en su mayoría irrelevantes para consideraciones prácticas, y uno puede construir gramáticas de acuerdo con la semántica informal dada. Las propiedades prácticas del modelo son similares a las de las , mientras que las capacidades descriptivas se mejoran aún más. En particular, se conservan algunas propiedades prácticamente útiles heredadas de gramáticas libres de contexto, como los algoritmos de análisis eficientes, ver . (es) |
| dbo:wikiPageExternalLink | http://www.di.uoa.gr/%7Eprondo/papers/knr09.pdf http://users.utu.fi/aleokh/boolean/ http://users.utu.fi/aleokh/papers/boolean_matrix.pdf https://web.archive.org/web/20160303230513/http:/users.utu.fi/aleokh/papers/boolean_matrix.pdf https://pdfs.semanticscholar.org/2fd5/9363120a1576a3aa7b3cabec3117ca414472.pdf |
| dbo:wikiPageID | 3237784 (xsd:integer) |
| dbo:wikiPageLength | 4163 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1106134892 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:International_Conference_on_Developments_in_Language_Theory dbr:Negation dbr:Conjunctive_grammar dbr:Logical_conjunction dbr:Language_equation dbr:Lecture_Notes_in_Computer_Science dbr:Logic_programming dbr:Formal_grammar dbr:Formal_language dbr:Logical_disjunction dbc:Formal_languages dbr:Context-free_grammars |
| dbp:date | 2016-03-03 (xsd:date) |
| dbp:url | https://web.archive.org/web/20160303230513/http:/users.utu.fi/aleokh/papers/boolean_matrix.pdf |
| dbp:wikiPageUsesTemplate | dbt:Cite_techreport dbt:Cite_book dbt:Cite_journal dbt:Harvtxt dbt:Ill dbt:Webarchive dbt:Formalmethods-stub |
| dcterms:subject | dbc:Formal_languages |
| rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 yago:WikicatFormalLanguages |
| rdfs:comment | Boolean grammars, introduced by , are a class of formal grammars studied in formal language theory. They extend the basic type of grammars, the context-free grammars, with conjunction and negation operations. Besides these explicit operations, Boolean grammars allow implicit disjunction represented by multiple rules for a single nonterminal symbol, which is the only logical connective expressible in context-free grammars. Conjunction and negation can be used, in particular, to specify intersection and complement of languages. An intermediate class of grammars known as conjunctive grammars allows conjunction and disjunction, but not negation. (en) Las gramáticas booleanas, introducidas por Okhotin, son una clase de gramáticas formales estudiadas en la teoría de lenguajes formales. Esta gramáticas extienden el tipo básico de gramáticas, las gramáticas libres de contexto con operaciones de conjunción y negación. Además de estas operaciones explícitas, las gramáticas booleanas permiten la disyunción implícita representada por múltiples reglas para un solo símbolo no terminal, que es la única conectividad lógica expresable en gramáticas libres de contexto. La conjunción y la negación pueden usarse, en particular, para especificar la intersección y el complemento de los idiomas. Una clase intermedia de gramáticas conocidas como permite la conjunción y la disyunción pero no la negación. (es) |
| rdfs:label | Boolean grammar (en) Gramática booleana (es) |
| owl:sameAs | freebase:Boolean grammar yago-res:Boolean grammar wikidata:Boolean grammar dbpedia-es:Boolean grammar https://global.dbpedia.org/id/4ancN |
| prov:wasDerivedFrom | wikipedia-en:Boolean_grammar?oldid=1106134892&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Boolean_grammar |
| is dbo:wikiPageWikiLink of | dbr:Scannerless_parsing dbr:Index_of_philosophy_articles_(A–C) dbr:Conjunctive_grammar dbr:Comparison_of_parser_generators dbr:Parsing_expression_grammar dbr:Language_equation dbr:Syntactic_predicate dbr:Scannerless_Boolean_Parser |
| is foaf:primaryTopic of | wikipedia-en:Boolean_grammar |