Every formal language is a subset of E*.

Let's say this formal language is python. If a program is syntactically correct, then the Python Automata accepts the "word", which is the program. If that is true, what are the atomic elements like "print" called?

Is this correct? Please correct my thought on this.


1 Answer 1


I think that your intuition is correct but the exact details of its explanation are fuzzy. Every syntactically correct program is a "word" or a "sentence" (depends on what you prefer) of some language $\mathcal{L}$.

In the context of lexer-full parsing, the "automaton" (intended as the program that prints "syntax error" in case of error) that accepts the language is composed of 2 distinct automata that cooperate to decide whether $\mathcal{p}\in\mathcal{L}$. They are the lexer and the parser.

The former is responsible for accepting the sequence of keywords and basic constructs of the language (int, for, while, print, +, -, numbers,...).

The latter is responsible for checking that sequences of non-terminal and terminal symbols (keywords and their sequences) form correct sentences.

Namely, the lexer is able to tell that "for" is a word of the language, but is unable to tell that "for while () }}}" makes no sense. That's the purpose of the parser.

Since both automata (lexer and parser) are accepting a language, all the sequences of characters or symbols accepted are words of their languages.

In general, informally, the lexer accepts words, while the parser accepts sentences. This is simply a handy way to distinguish sequences of characters from sequences of symbols read by the lexer. Still, there's no strict nomenclature.

  • $\begingroup$ So "sentences" are just the words, which is accepted of the "parser" automata so to say, @Chaos? $\endgroup$
    – David
    Aug 24, 2021 at 10:33
  • 1
    $\begingroup$ Exactly. My conclusion is that words and sentences are synonyms. Some people use the difference to point out which automaton is responsible for acceptance. Notice that, in the context of scanner-less parsing, there's no lexer and in that case, keywords are read directly by the parser. Eventually, words and sentences are the same things. $\endgroup$
    – Chaos
    Aug 24, 2021 at 10:35
  • $\begingroup$ There might be a slight difference between words and sentences in this context. (But I might be wrong.) When reading int for the lexer these are three symbols. For the parser it already acts as a single symbol as it was decided by the lexer that this sequence represents a keyword. Summarizing, the alfabet changes. $\endgroup$ Aug 24, 2021 at 23:00
  • $\begingroup$ @HendrikJan I think, we are talking about different contexts. I am trying to really see this from an automata perspective, which accepts different words. How these words are accepted (through first lexing and then parsing or just parsing or asking for some simple condition does not matter). When you are talking about sentences from the compiler perspective, you are talking about (i surmize!) a sentence, which represent one "action", but in my above context a word/sentence is really for example written code of any program like linux or emacs for example. Please correct me on this. $\endgroup$
    – David
    Aug 25, 2021 at 8:32
  • $\begingroup$ @Hendrik Jan Well yes, the alphabet changes, that comes from the definition of each automaton. The lexer can read single characters, the parser can as well but is primarily designed to read sequences of terminal and non-terminal symbols. Eventually, words and sentences are just sequences of symbols of the alphabet so it is customary to use one term or another. $\endgroup$
    – Chaos
    Aug 25, 2021 at 8:46

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.