|
Penttonen Normal Form
In formal language theory, a context-sensitive grammar is in Kuroda normal form if all production rules are of the form: :''AB'' → ''CD'' or :''A'' → ''BC'' or :''A'' → ''B'' or :''A'' → ''a'' where A, B, C and D are nonterminal symbols and ''a'' is a terminal symbol. Some sources omit the ''A'' → ''B'' pattern. It is named after Sige-Yuki Kuroda, who originally called it a linear bounded grammar—a terminology that was also used by a few other authors thereafter. Every grammar in Kuroda normal form is noncontracting, and therefore, generates a context-sensitive language. Conversely, every context-sensitive language which does not generate the empty string can be generated by a grammar in Kuroda normal form. A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: ''AB'' → ''CD'' is replaced by four context-sensitive rules ''AB'' → ''AZ'', ''AZ'' → ''WZ'', ''WZ'' → ''WD'' and ''WD'' → ''CD''. This te ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Formal Language Theory
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symbols, letters, or tokens that concatenate into strings of the language. Each string concatenated from symbols of this alphabet is called a word, and the words that belong to a particular formal language are sometimes called ''well-formed words'' or ''well-formed formulas''. A formal language is often defined by means of a formal grammar such as a regular grammar or context-free grammar, which consists of its formation rules. In computer science, formal languages are used among others as the basis for defining the grammar of programming languages and formalized versions of subsets of natural languages in which the words of the language represent concepts that are associated with particular meanings or semantics. In computational complexity t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Context-sensitive Grammar
A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are languages that can be described by CSG but not by context-free grammars. Context-sensitive grammars are less general (in the same sense) than unrestricted grammars. Thus, CSG are positioned between context-free and unrestricted grammars in the Chomsky hierarchy. A formal language that can be described by a context-sensitive grammar, or, equivalently, by a noncontracting grammar or a linear bounded automaton, is called a context-sensitive language. Some textbooks actually define CSGs as non-contracting, although this is not how Noam Chomsky defined them in 1959. This choice of definition makes no difference in terms of the languages generated (i.e. the two definitions are weakly equiva ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nonterminal
In computer science, terminal and nonterminal symbols are the lexical elements used in specifying the production rules constituting a formal grammar. ''Terminal symbols'' are the elementary symbols of the language defined by a formal grammar. ''Nonterminal symbols'' (or ''syntactic variables'') are replaced by groups of terminal symbols according to the production rules. The terminals and nonterminals of a particular grammar are two disjoint sets. Terminal symbols Terminal symbols are literal symbols that may appear in the outputs of the production rules of a formal grammar and which cannot be changed using the rules of the grammar. Applying the rules recursively to a source string of symbols will usually terminate in a final output string consisting only of terminal symbols. Consider a grammar defined by two rules. Using pictoric marks interacting with each other: # The symbol ר can become ди # The symbol ר can become д Here д is a terminal symbol because no rule ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Terminal Symbol
In computer science, terminal and nonterminal symbols are the lexical elements used in specifying the production rules constituting a formal grammar. ''Terminal symbols'' are the elementary symbols of the language defined by a formal grammar. ''Nonterminal symbols'' (or ''syntactic variables'') are replaced by groups of terminal symbols according to the production rules. The terminals and nonterminals of a particular grammar are two disjoint sets. Terminal symbols Terminal symbols are literal symbols that may appear in the outputs of the production rules of a formal grammar and which cannot be changed using the rules of the grammar. Applying the rules recursively to a source string of symbols will usually terminate in a final output string consisting only of terminal symbols. Consider a grammar defined by two rules. Using pictoric marks interacting with each other: # The symbol ר can become ди # The symbol ר can become д Here д is a terminal symbol because no rule ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sige-Yuki Kuroda
, aka S.-Y. Kuroda, was Professor Emeritus and Research Professor of Linguistics at the University of California, San Diego. Although a pioneer in the application of Chomskyan generative syntax to the Japanese language, he is known for the broad range of his work across the language sciences. For instance, in formal language theory, the Kuroda normal form for context-sensitive grammars bears his name. Early life and career Kuroda was born into a prominent family of mathematicians in Japan. His grandfather, Teiji Takagi, was a student of David Hilbert. Kuroda himself received degrees in mathematics and linguistics from the University of Tokyo. In 1962, he entered MIT with the first graduating class from the new Department of Linguistics, where he wrote his seminal dissertation, ''Generative Studies in the Japanese Language'' (1965) under Chomsky's supervision. Important publications * "Classes of languages and linear-bounded automata", Information and Control, 7(2): 207–223, Ju ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Noncontracting Grammar
In formal language theory, a grammar is noncontracting (or monotonic) if all of its production rules are of the form α → β where α and β are strings of nonterminal and terminal symbols, and the length of α is less than or equal to that of β, , α, ≤ , β, , that is β is not shorter than α. A grammar is essentially noncontracting if there may be one exception, namely, a rule ''S'' → ε where ''S'' is the start symbol and ε the empty string, and furthermore, ''S'' never occurs in the right-hand side of any rule. None of the rules of a noncontracting grammar decreases the length of the string that is being rewritten. If each rule even properly increases the length, the grammar is called a growing context-sensitive grammar. History Chomsky (1963) called a noncontracting grammar a type 1 grammar; in the same work, he called a context-sensitive grammar a "type 2 grammar", and he proved that these two are weakly equivalent (context-free grammars were des ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Context-sensitive Language
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 one of the four types of grammars in the Chomsky hierarchy. Computational properties 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 kn cells, where n is the size of the input and k 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, e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Empty String
In formal language theory, the empty string, or empty word, is the unique string of length zero. Formal theory Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special case where the sequence has length zero, so there are no symbols in the string. There is only one empty string, because two strings are only different if they have different lengths or a different sequence of symbols. In formal treatments, the empty string is denoted with ε or sometimes Λ or λ. The empty string should not be confused with the empty language ∅, which is a formal language (i.e. a set of strings) that contains no strings, not even the empty string. The empty string has several properties: * , ε, = 0. Its string length is zero. * ε ⋅ s = s ⋅ ε = s. The empty string is the identity element of the concatenation operation. The set of all strings forms a free monoid with respect to ⋅ and ε. * εR = ε. Reversal ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Unrestricted Grammar
In automata theory, the class of unrestricted grammars (also called semi-Thue, type-0 or phrase structure grammars) is the most general class of grammars in the Chomsky hierarchy. No restrictions are made on the productions of an unrestricted grammar, other than each of their left-hand sides being non-empty. This grammar class can generate arbitrary recursively enumerable languages. Formal definition An unrestricted grammar is a formal grammar G = (N, T, P, S), where * N is a finite set of nonterminal symbols, * T is a finite set of terminal symbols with N and T disjoint,Actually, T\cap N=\emptyset is not strictly necessary since unrestricted grammars make no real distinction between the two. The designation exists purely so that one knows when to stop generating sentential forms of the grammar; more precisely, the language L(G) recognized by G is restricted to strings of terminal symbols. * P is a finite set of production rules of the form \alpha \to \beta , where \alpha ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Weak Equivalence (formal Languages)
In formal language theory, weak equivalence of two grammars means they generate the same set of strings, i.e. that the formal language they generate is the same. In compiler theory the notion is distinguished from strong (or structural) equivalence, which additionally means that the two parse trees are reasonably similar in that the same semantic interpretation can be assigned to both. Vijay-Shanker and Weir (1994) demonstrates that Linear Indexed Grammars, Combinatory Categorial Grammars, Tree-adjoining Grammars, and Head Grammars are weakly equivalent formalisms, in that they all define the same string languages. On the other hand, if two grammars generate the same set of derivation trees (or more generally, the same set of abstract syntactic objects), then the two grammars are strongly equivalent. Chomsky (1963) introduces the notion of strong equivalence, and argues that only strong equivalence is relevant when comparing grammar formalisms. Kornai and Pullum (1990)Kornai, A ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Backus–Naur Form
In computer science, Backus–Naur form () or Backus normal form (BNF) is a metasyntax notation for context-free grammars, often used to describe the syntax of languages used in computing, such as computer programming languages, document formats, instruction sets and communication protocols. It is applied wherever exact descriptions of languages are needed: for instance, in official language specifications, in manuals, and in textbooks on programming language theory. Many extensions and variants of the original Backus–Naur notation are used; some are exactly defined, including extended Backus–Naur form (EBNF) and augmented Backus–Naur form (ABNF). Overview A BNF specification is a set of derivation rules, written as ::= __expression__ where: * is a '' nonterminal'' (variable) and the __expression__ consists of one or more sequences of either terminal or nonterminal symbols; * means that the symbol on the left must be replaced with the expression on the right. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chomsky Normal Form
In formal language theory, a context-free grammar, ''G'', is said to be in Chomsky normal form (first described by Noam Chomsky) if all of its production rules are of the form: : ''A'' → ''BC'', or : ''A'' → ''a'', or : ''S'' → ε, where ''A'', ''B'', and ''C'' are nonterminal symbols, the letter ''a'' is a terminal symbol (a symbol that represents a constant value), ''S'' is the start symbol, and ε denotes the empty string. Also, neither ''B'' nor ''C'' may be the start symbol, and the third production rule can only appear if ε is in ''L''(''G''), the language produced by the context-free grammar ''G''. Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent onethat is, one that produces the same language which is in Chomsky normal form and has a size no larger than the square of the original grammar's size. Converting a grammar to Chomsky normal form To convert a grammar to C ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
