Scholarlink

Nondeterminism is a concept that is not inherently self-dual in the following sense: a nondeterministic automaton may intuitively “guess” at some point to make a choice that turns out to be good for accepting a word. This is why it is typically easy to construct NFA for languages which are defined via existential quantification, for instance \(\sum^{*} aba\sum^{*}\) – the set of all words for which there is a subword of the form aba. Consider, however, its complement – the set of all words that do not contain the subword aba.

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

Alternating Finite Automata

  • 章节

  • 发表日期：

    2025年

查看全文
  • Martin Hofmann,
  • Martin Lange

摘要

Nondeterminism is a concept that is not inherently self-dual in the following sense: a nondeterministic automaton may intuitively “guess” at some point to make a choice that turns out to be good for accepting a word. This is why it is typically easy to construct NFA for languages which are defined via existential quantification, for instance \(\sum^{*} aba\sum^{*}\) – the set of all words for which there is a subword of the form aba. Consider, however, its complement – the set of all words that do not contain the subword aba.