Whether there exists a Deterministic Infinite Automata (DIA), which accepts all strings in $L$ and rejects all strings not in $L$?

137 Views Asked by At

Given an automata DIA $I = (Q,\Sigma,\delta,q_0,F)$, and the set of states $Q$ is infinite. The set of characters $\Sigma$ is still finite.

Wondering whether there is an $I$ and an arbitrary language $L$ over $\Sigma$, such that $I$ accepts all strings in $L$ and rejects all strings not in $L$?

1

There are 1 best solutions below

1
On

Welcome to MSE!

Hint: Build a tree of all possible words in $\Sigma^*$. Put accepting states wherever you need them to go.


I hope this helps ^_^