Kind of what it says on the tin. Let's say I have a countably infinite alphabet $A$ and a "language" $L = \{s_1s_2 | s_1,s_2 \in A\}$ (i.e. all possible strings of length 2). Now, my question is this: does it even make sense to think of this in terms of formal languages? Is there some construct akin to a state machine that I can use to model such a thing? And do any of the above answers change if $A$ is uncountable?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ The main practical difference would be that you would no Longer be able to draw the state machine on paper :) each state just needs a transition function to decide the next state based on the current symbol, so this would work for infinitely many symbols based on the fact that functions work on an infinite domain $\endgroup$– Kurt MuellerCommented Dec 11, 2016 at 2:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The definition of formal language doesn't depend on the alphabet - it remains exactly the same. Things start getting a bit more complicated when you are interested in certain classes of languages. For example, let us consider regular languages. If your alphabet is infinite, the restriction of having only finitely many states seems a bit restrictive. Instead, it makes sense to allow any number of states whose cardinal is strictly less than that of the alphabet (if you allow a cardinal at least as large, every language would be regular). The corresponding notion of regular languages isn't too exciting perhaps, but at least it is a genuine subclass of all languages, which shares some properties with regular languages over finite alphabets.
answered Dec 11, 2016 at 8:35