In the area of picture languages, many mechanisms have been studied to describe language classes, often inspired by what has been done before for string languages. Following this tradition, we are now introducing a pushdown automaton (PDA) extension of two previously defined variants of finite automata (FA) working on arrays, namely boustrophedon finite automata (BFA) and returning finite automata (RFA), leading to BPDA and RPDA, respectively. While BFA and RFA characterize the same class of array languages, BPDA and RPDA turn out to describe incomparable classes of array languages. We also prove that BPDA and RPDA can be viewed as a proper generalization of context-free matrix languages, which is interesting, as it is known that (apart from a transposition) BFA and RFA characterize the regular matrix languages.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Boustrophedon Pushdown Automata for Two-Dimensional Picture Languages

  • Henning Fernau,
  • R. Jennifer Rose,
  • Robinson Thamburaj,
  • D. Gnanaraj Thomas

摘要

In the area of picture languages, many mechanisms have been studied to describe language classes, often inspired by what has been done before for string languages. Following this tradition, we are now introducing a pushdown automaton (PDA) extension of two previously defined variants of finite automata (FA) working on arrays, namely boustrophedon finite automata (BFA) and returning finite automata (RFA), leading to BPDA and RPDA, respectively. While BFA and RFA characterize the same class of array languages, BPDA and RPDA turn out to describe incomparable classes of array languages. We also prove that BPDA and RPDA can be viewed as a proper generalization of context-free matrix languages, which is interesting, as it is known that (apart from a transposition) BFA and RFA characterize the regular matrix languages.