regular - 2023 Penn Bowl - Buzzpoints App

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

Back to bonuses

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%
2023 Penn Bowl @ Waterloo	10/28/2023	N	4	20.00	75%	75%	50%
2023 Penn Bowl @ FSU	10/28/2023	N	1	0.00	0%	0%	0%
2023 Penn Bowl (Norcal)	10/28/2023	N	1	30.00	100%	100%	100%
2023 Penn Bowl (UK)	10/28/2023	N	4	15.00	50%	50%	50%

Data


Brown	MIT	0	0	0	0
UMD B	Columbia B	0	0	0	0
John Jay	Cornell B	10	10	10	30
NYU	JHU A	0	0	10	10
Columbia A	Rutgers	10	0	0	10