Question
Proving Kleene’s (“KLAY-nee’s”) theorem involves developing an algorithm to convert these strings into DFAs. For 10 points each:
[10m] Name these strings used for pattern matching in text with tools like Python’s “re” module. A textbook application of these strings is to check whether an email address is valid.
ANSWER: regular expressions [or regex] (“DFA” stands for “deterministic finite automaton.”)
[10h] This Ken Thompson–developed command line tool, which is commonly used alongside sed and awk, prints lines that match a given regular expression. This tool’s “c” flag makes it return only the number of matches in each queried file.
ANSWER: grep [or global regular expression print or global slash regular expression search slash and print]
[10e] A regular expression can define a “regular” one of these sets. ChatGPT relies on an LLM, or “large” model of these sets.
ANSWER: formal languages [accept regular languages; accept large language model]
<David Bass, Science - Computer Science> ~23206~ <Editor: David Bass>
Data
| Team | Opponent | Part 1 | Part 2 | Part 3 | Total |
|---|---|---|---|---|---|
| Alabama Cyber Tech | University Lab | 0 | 0 | 0 | 0 |
| Barrington | Saint Joseph | 0 | 10 | 10 | 20 |
| Belmont | Detroit Catholic Central C | 10 | 0 | 10 | 20 |
| Canyon Crest | Owensboro | 0 | 0 | 10 | 10 |
| Carbondale | Lightridge | 0 | 0 | 10 | 10 |
| Chattahoochee | Fairfield County AT | 0 | 0 | 10 | 10 |
| Choate Rosemary Hall | Winston Churchill A | 10 | 10 | 10 | 30 |
| Heights | Stevenson A | 10 | 0 | 10 | 20 |
| Hoover A | Beavercreek | 10 | 0 | 10 | 20 |
| Hunter A | Hoover B | 0 | 0 | 10 | 10 |
| James W. Robinson | DuPage County AT | 0 | 0 | 0 | 0 |
| Johns Creek A | Maggie Walker C | 10 | 10 | 10 | 30 |
| Johns Creek B | St. Thomas | 10 | 0 | 10 | 20 |
| Kinkaid | Thomas Jefferson D | 10 | 10 | 10 | 30 |
| Lambert | Bloomington | 10 | 10 | 10 | 30 |
| Lindbergh | St. Xavier | 0 | 0 | 10 | 10 |
| Livingston A | Norfolk Academic Guild | 10 | 0 | 10 | 20 |
| Maggie Walker A | Detroit Catholic Central A | 0 | 0 | 10 | 10 |
| McLean B | Cincinnati Hills | 0 | 0 | 10 | 10 |
| Mexico | Downingtown STEM | 0 | 0 | 0 | 0 |
| Northmont A | Great Valley | 0 | 0 | 10 | 10 |
| Okemos | Northmont B | 10 | 0 | 0 | 10 |
| Richard Montgomery A | Seven Lakes | 0 | 0 | 10 | 10 |
| Richard Montgomery B | Detroit Catholic Central B | 0 | 0 | 0 | 0 |
| St. Mark's | Maggie Walker B | 10 | 0 | 10 | 20 |
| Strake Jesuit | McLean A | 0 | 0 | 0 | 0 |
| Thomas Jefferson A | Elkhorn North | 10 | 0 | 10 | 20 |
| Thomas Jefferson C | Hastings | 0 | 0 | 10 | 10 |
| Walter Payton A | Durham AT | 0 | 0 | 10 | 10 |
Summary
| Tournament | Edition | Exact Match? | Heard | PPB | Easy % | Medium % | Hard % |
|---|---|---|---|---|---|---|---|
| 2024 PACE NSC | 06/08/2024 | Y | 29 | 13.79 | 79% | 41% | 17% |