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>

Back to bonuses

Summary

2023 Penn Bowl @ Waterloo10/28/2023Y420.0075%75%50%
2023 Penn Bowl @ FSU10/28/2023Y10.000%0%0%
2023 Penn Bowl (Norcal)10/28/2023Y130.00100%100%100%
2023 Penn Bowl (UK)10/28/2023Y415.0050%50%50%

Data

StanfordBerkeley B10101030