Scary formalisms
This is a potentially infinite set of strings of terminal symbols generated by a grammar.
What is a language?
This is the number of parts, into which a word must be split for the Pumping Lemma for regular languages.
What is 3?
This kind of state lets us know whether a word is accepted or not.
What is an end state?
This datastructure represents a simple form of memory in push-down automata.
What is a stack?
w = xyz in L
|y| ge 1
|xy| le p_L
forall n ge 0: xy^nz in L
What is the pumping lemma (for regular languages)?
This logical rule of inference is used to show with the Pumping Lemma that a language is not regular or context-free respectively.
What is modus tollens?
This attribute of a function makes the difference between an NFA and a DFA.
What is total?
This component (or module) of natural language is definitely "irregular".
What is syntax?
This is the simplest regular expression that describes the language with the words "aba", "ababa", "abababa", "ababababa", ..., but not with the word "a"
What is
a(ba)^+
?
Considering a split of a word in 5 pieces, these ordinal numbers determine the parts that can be pumped if the word belongs to a context-free language.
What are "second" and "forth"?
This set is a part of the argument of the state-transition function and corresponds to the symbols of a word, which the automaton should read.
What is the input alphabet?
In 1985, this linguist destroyed all hopes of natural languages being context-free based on the language of the chocolate lovers.
Who is (Stuart M.) Shieber?