Question
On the Chomsky hierarchy, these languages are generated by a type-3 grammar. For 10 points each:
[10e] Identify this word, which describes expressions that are used to match patterns in strings. Kleene’s theorem states that expressions described by this word are equivalent to finite state automaton.
ANSWER: regular [or regular expression; or regular language]
[10h] The weaker version of this statement can be used to prove that a language is not regular. The crucial part of this statement involves dividing a given string into three substrings, x, y, and z, and then for all integers n, xy^n z is also in the language if it is indeed regular.
ANSWER: pumping lemma
[10m] A context-free grammar generates a non-regular language that is recognized by an automaton that employs one of these things. A pushdown automaton can read the top of these things and manipulate them.
ANSWER: stack
<Leo Law, Other Science>
Summary
| 2023 Penn Bowl (Harvard) | 10/21/2023 | Y | 1 | 0.00 | 0% | 0% | 0% |
| 2023 Penn Bowl (Mainsite) | 10/21/2023 | Y | 4 | 12.50 | 50% | 50% | 25% |
Data
| Brown | MIT | 0 | 0 | 0 | 0 |