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$

2 Answers 2

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

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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