Orientifold: Difference between revisions
en>ZéroBot m r2.7.1) (robot Adding: ko:오리엔티폴드 |
en>Addbot m Bot: Migrating 2 interwiki links, now provided by Wikidata on d:q3356307 |
||
| Line 1: | Line 1: | ||
In [[theoretical computer science]] and [[formal language theory]], a '''prefix grammar''' is a type of [[string rewriting system]], consisting of a set of [[string (computer science)|string]] [[rewriting]] rules, and similar to a [[formal grammar]] or a [[semi-Thue system]]. What is specific about prefix grammars is not the shape of their rules, but the way in which they are applied: only [[prefix (computer science)|prefixes]] are rewritten. The prefix grammars describe exactly all [[regular language]]s.<ref>[http://portal.acm.org/citation.cfm?id=185820 M. Frazier and C. D. Page. Prefix grammars: An alternative characterization of the regular languages. Information Processing Letters, 51(2):67–71, 1994.]</ref> | |||
==Formal definition== | |||
A prefix grammar ''G'' is a [[n-tuple|3-tuple]], (Σ, ''S'', ''P''), where | |||
*Σ is a finite alphabet | |||
*''S'' is a finite set of base strings over Σ | |||
*''P'' is a set of production rules of the form ''u'' → ''v'' where ''u'' and ''v'' are strings over Σ | |||
For strings ''x'', ''y'', we write ''x →<sub>G</sub> y'' (and say: ''G'' can derive ''y'' from ''x'' in one step) if there are strings ''u, v, w'' such that ''x = vu, y = wu'', and ''v → w'' is in ''P''. Note that ''→<sub>G</sub>'' is a [[binary relation]] on the strings of Σ. | |||
The ''language'' of ''G'', denoted ''L(G)'', is the set of strings derivable from ''S'' in zero or more steps: formally, the set of strings ''w'' such that for some ''s'' in ''S'', ''s R w'', where ''R'' is the [[transitive closure]] of ''→<sub>G</sub>''. | |||
==Example== | |||
The prefix grammar | |||
*Σ = {0, 1} | |||
*''S'' = {01, 10} | |||
*''P'' = {0 → 010, 10 → 100} | |||
describes the language defined by the [[regular expression]] | |||
:<math> 01(01)^* \cup 100^* </math> | |||
==See also == | |||
* [[Regular grammar]] | |||
==References== | |||
{{reflist}} | |||
[[Category:Formal languages]] | |||
Revision as of 20:34, 11 March 2013
In theoretical computer science and formal language theory, a prefix grammar is a type of string rewriting system, consisting of a set of string rewriting rules, and similar to a formal grammar or a semi-Thue system. What is specific about prefix grammars is not the shape of their rules, but the way in which they are applied: only prefixes are rewritten. The prefix grammars describe exactly all regular languages.[1]
Formal definition
A prefix grammar G is a 3-tuple, (Σ, S, P), where
- Σ is a finite alphabet
- S is a finite set of base strings over Σ
- P is a set of production rules of the form u → v where u and v are strings over Σ
For strings x, y, we write x →G y (and say: G can derive y from x in one step) if there are strings u, v, w such that x = vu, y = wu, and v → w is in P. Note that →G is a binary relation on the strings of Σ.
The language of G, denoted L(G), is the set of strings derivable from S in zero or more steps: formally, the set of strings w such that for some s in S, s R w, where R is the transitive closure of →G.
Example
The prefix grammar
- Σ = {0, 1}
- S = {01, 10}
- P = {0 → 010, 10 → 100}
describes the language defined by the regular expression
See also
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.