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 (x-y-to-the-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 @ Waterloo | 10/28/2023 | Y | 4 | 20.00 | 75% | 75% | 50% |
| 2023 Penn Bowl @ FSU | 10/28/2023 | Y | 1 | 0.00 | 0% | 0% | 0% |
| 2023 Penn Bowl (Norcal) | 10/28/2023 | Y | 1 | 30.00 | 100% | 100% | 100% |
| 2023 Penn Bowl (UK) | 10/28/2023 | Y | 4 | 15.00 | 50% | 50% | 50% |
Data
| Stanford | Berkeley B | 10 | 10 | 10 | 30 |