Detail publikace

Phrase-Structure Grammars: Normal Forms and Reduction

KŘIVKA, Z. MEDUNA, A. ZEMEK, P.

Originální název

Phrase-Structure Grammars: Normal Forms and Reduction

Typ

článek v časopise ve Web of Science, Jimp

Jazyk

angličtina

Originální abstrakt

This paper establishes two new normal forms for phrase-structure grammars in which both context-free rules and non-context-free rules are in prescribed forms. In addition, a limit is placed on the number of context-free rules. More specifically, the first form has 2 + n context-free rules, where n is the number of terminals. Concerning non-context-free rules, each of them has the form AB -> CD, where A, B, C, D are nonterminals. The second normal form has always only two context-free rules---S -> S# and # -> e, where S is the start symbol, # is a nonterminal, and e is the empty string. Regarding non-context-free rules, each of them is of the form AB -> XD, where A, B, D are nonterminals and X is a nonterminal or a terminal.

Klíčová slova

formal languages, phrase-structure grammars, normal forms

Autoři

KŘIVKA, Z.; MEDUNA, A.; ZEMEK, P.

Vydáno

31. 1. 2016

ISSN

0010-4620

Periodikum

COMPUTER JOURNAL

Ročník

59

Číslo

8

Stát

Spojené království Velké Británie a Severního Irska

Strany od

1180

Strany do

1185

Strany počet

6

URL

https://www.fit.vut.cz/research/publication/9949/

BibTex

@article{BUT130900,
  author="Zbyněk {Křivka} and Alexandr {Meduna} and Petr {Zemek}",
  title="Phrase-Structure Grammars: Normal Forms and Reduction",
  journal="COMPUTER JOURNAL",
  year="2016",
  volume="59",
  number="8",
  pages="1180--1185",
  doi="10.1093/comjnl/bxw001",
  issn="0010-4620",
  url="https://www.fit.vut.cz/research/publication/9949/"
}