0
$\begingroup$

I want to ask about the definition of regular languages. My book says there has to exist a deterministic finite automaton that recognizes it. Does this mean the finite automaton recognizes exactly this language and nothing else or it can recognize possibly some other words not in the language?

$\endgroup$
0
$\begingroup$

It means the automaton recognizes exactly it. in fact, you can even build an automaton that accepts every word (try to do it yourself), so there would be no meaning in the other definition

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

You can think of it as of a correct implementation of an algorithm in different programming languages. No matter which implementation you choose they all do exactly the same thing described by the algorithm.

Regular expressions or deterministic finite automata are just two different "programming languages" for implementing a regular language. If an automaton imlements the language correctly, it will recognize exactly the same set of words that are in the language.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.