Open AccessSuccinctness of Descriptions of Context-Free, Regular, and Finite Languages
Author(s) -
Evanthia Kalpazidou Schmidt
Publication year - 1978
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v7i84.6500
Subject(s) - succinctness , nondeterministic algorithm , pushdown automaton , deterministic pushdown automaton , nondeterministic finite automaton , nested word , regular expression , deterministic context free grammar , complement (music) , mathematics , finite state machine , discrete mathematics , quantum finite automata , ω automaton , regular language , deterministic finite automaton , rule based machine translation , automata theory , automaton , computer science , context free grammar , theoretical computer science , algorithm , tree adjoining grammar , programming language , artificial intelligence , chemistry , biochemistry , complementation , gene , phenotype
This thesis analyzes the descriptional power of finite automata, regular expressions, pushdown automata, and certain generalized models of macro grammars. For finite automata and pushdown automata the emphasis is on ambiguity. It is shown that ambiguous nondeterminism allows more succinct definitions than unambiguous nondeterminism which in turn allows more succinct definitions than determinism. The succinctness gain is nonrecursive for pda's and nonpolynomial for finite automata. The succinctness of regular expressions and macro grammars is measured in terms of complexity theory. It is shown that the inequivalence problem for Ol macro grammars generating finite languages is hard for nondeterministic double exponential time, and that the ''nonemptiness of complement'' problem for unambiguous regular expressions is in NP. This implies that unambiguous regular expressions are ''easier'' than general regular expressions (unless NP is equal to PSPACE).