Jump to content

Talk:Omega language

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

How can membership of $\omega$-regular languages be decidable?

[edit]

If you say something is decidable unqualified then that means it's decidable by a Turing Machine. There is no way that membership of the language $\{a\}^\omega$ over the alphabet $\Sigma=\{a,b\}$ is decidable by a Turing machine. The articles on similar topics seem to make similar dubious or incorrect claims. — Preceding unsigned comment added by 62.172.100.253 (talk) 17:04, 2 January 2018 (UTC)[reply]


It's perfectly standard usage to extend the concept of decidability to other models of computation. See paragraph 2 of Recursive language. In this case, as the text explains, these languages are decidable with a Buchi automaton. — Preceding unsigned comment added by 131.252.62.244 (talk) 16:51, 18 October 2018 (UTC)[reply]