py4kidsSearch

Contest Python: ACSL › Unit 11 — FSAs and Regular Expressions

Exercises: Unit 11 — FSAs and Regular Expressions

There are two kinds of exercises here, just as on an ACSL contest.

  • Short-answer: work it out with pencil and paper and write one exact answer.
    • Most questions give options labelled A, B, C, …. Write the labels of every option that qualifies, in alphabetical order, separated by a comma and a space: A, C, D. If no option qualifies, write NONE.
    • Write a state exactly as the table names it (q1), and a count as a whole number (6).
  • Programming: write a complete program that reads the input with input() and prints exactly the output described. Save it as a .py file and run it from a terminal, typing the sample input or feeding it a file. Do not use Python's re module: the point is to write the checking yourself.

Every FSA is given as a transition table: → marks the initial state, (final) marks each final state, and — means there is no transition (a string that needs it is rejected). In a regular expression, | and U both mean union, and λ is the empty string.

FSAs and regular expressions are on the Intermediate and Senior papers only, so each exercise is marked Intermediate or Senior: the lowest division it belongs to. Do every exercise at or below your division. Exercises marked Challenge are extra practice for when you want more.

Exercise 1: Ending Right

  • Division: Intermediate

Consider this FSA over the alphabet a, b.

state a b
→ q0 q1 q0
q1 q1 q2
q2 (final) q1 q0

Which of these strings does the FSA accept? Choose every one that it accepts.

  • A. ab
  • B. abb
  • C. bbab
  • D. aabab
  • E. ba

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Exercise 2: Where Does It Stop?

  • Division: Intermediate

Consider this FSA over the alphabet 0, 1.

state 0 1
→ q0 (final) q0 q1
q1 q2 q0
q2 q1 q2

The FSA reads the string 10110. In which state is it after reading the last symbol?

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: A state, written exactly as the table names it (as in `q0`).

For parents and teachers: report a problem

Exercise 3: Missing Moves

  • Division: Intermediate

Consider this FSA over the alphabet a, b.

state a b
→ q0 (final) q1 —
q1 — q0

Which of these strings does the FSA accept? Choose every one that it accepts.

  • A. λ (the empty string)
  • B. ab
  • C. aba
  • D. abab
  • E. ba

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Exercise 4: FSA Simulator

  • Division: Intermediate

Write a program that reads an FSA and some strings, and says which strings the FSA accepts.

The input is:

  1. one line with the name of the initial state
  2. one line with the names of the final states, separated by single spaces
  3. one line with a whole number t, the number of transitions
  4. t lines, each of the form state symbol next: in state state, reading symbol, move to state next
  5. one line with a whole number n, the number of strings to test
  6. n lines, each holding one string to test; a line holding just - stands for the empty string λ

For each of the n strings, in order, print ACCEPT if the FSA accepts it and REJECT if not. If the FSA needs a transition that is not in the list, the string is rejected.

Store the transitions in a dict whose keys are (state, symbol) tuples, as in the lesson.

Constraints

  • There are between 1 and 20 states, and each state name is a word of letters and digits.
  • Every symbol is a single small letter or digit.
  • t is between 1 and 100, and no (state, symbol) pair appears twice.
  • n is between 1 and 20, and each string has between 0 and 30 symbols (written - when it has 0).
  • A string may contain a symbol that no transition uses.

Sample Input

A
C
6
A a B
A b A
B a B
B b C
C a B
C b A
4
aab
ba
abab
-

Sample Output

ACCEPT
REJECT
ACCEPT
REJECT

The last string is empty, so the FSA stays in A, which is not final.

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output line by line.

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

For parents and teachers: report a problem

Exercise 5: Name That Language

  • Division: Intermediate

Consider this FSA over the alphabet a, b.

state a b
→ q0 q1 —
q1 q2 q1
q2 (final) — q2

Which regular expression describes exactly the strings that this FSA accepts?

  • A. ab*ab*
  • B. (ab*)*
  • C. ab*a|b*
  • D. a(b|a)*b*

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Exercise 6: Star First

  • Division: Intermediate

Which of these strings are described by the regular expression a|bc*?

  • A. a
  • B. bccc
  • C. acc
  • D. bcbc
  • E. b

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Exercise 7: Union Last

  • Division: Intermediate

Which of these strings are described by the regular expression (0U1)*00U11*?

  • A. 100
  • B. 111
  • C. 0110
  • D. 00
  • E. 10

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Exercise 8: Any Mixture

  • Division: Intermediate

Which of these regular expressions are equivalent to (a|b)*?

  • A. (a*b*)*
  • B. a*b*
  • C. a*(ba*)*
  • D. (ab)*
  • E. (a*|b*)*

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Exercise 9: Zero or More

  • Division: Intermediate

Which of these regular expressions are equivalent to a*?

  • A. aa*|λ
  • B. (a*)*
  • C. aa*
  • D. a*a
  • E. (λ|a)*

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Exercise 10: Capitals, Then Small

  • Division: Intermediate

Which of these strings match the regular expression [A-C]+[a-z]?[0-9]*?

  • A. AB
  • B. CAt77
  • C. Dog1
  • D. ABab5
  • E. B9

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Exercise 11: Any Middle Letter

  • Division: Intermediate

Which of these strings match the regular expression h.t[^aeiou]*?

  • A. hat
  • B. hoot
  • C. hits
  • D. h.tea
  • E. hxtz9

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Exercise 12: Pattern Checker

  • Division: Intermediate

A pattern is a line of small letters, where each letter may be followed by one of these marks:

  • ?: the letter appears zero times or once
  • +: the letter appears one or more times
  • *: the letter appears zero or more times

A letter with no mark appears exactly once. A word matches the pattern when the whole word can be read as the pattern, from its first character to its last. For example, ab?c+d* matches acc and abcd, but not abd (it needs at least one c).

The first line of input is the pattern. The second line holds a whole number n. Each of the next n lines holds one word; a line holding just - stands for the empty word λ. For each word, in order, print ACCEPT if it matches the pattern and REJECT if not.

Write the matching yourself, with a recursive function like the one in Lesson 3.

Constraints

  • The pattern has between 1 and 20 characters. It starts with a letter, and every mark comes straight after a letter.
  • n is between 1 and 20.
  • Each word has between 0 and 20 small letters (written - when it has 0).

Sample Input

ab?c+d*
6
acc
abcd
abd
abbc
acdd
ab

Sample Output

ACCEPT
ACCEPT
REJECT
REJECT
ACCEPT
REJECT

For the pattern a*b?, the empty word - prints ACCEPT; for the pattern a+, it prints REJECT.

How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output line by line.

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

For parents and teachers: report a problem

Exercise 13: Counting Accepted Strings

  • Division: Senior

Consider this FSA over the alphabet 0, 1.

state 0 1
→ q0 (final) q0 q1
q1 q2 q0
q2 q1 q2

How many strings of exactly 4 symbols does this FSA accept?

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: a number

For parents and teachers: report a problem

Exercise 14: Pick Every Description

  • Division: Senior

Consider this FSA over the alphabet a, b.

state a b
→ q0 (final) q1 q0
q1 q0 q1

Which of these regular expressions describe exactly the strings that this FSA accepts? Choose every one that does.

  • A. b*(ab*ab*)*
  • B. (aa|b)*
  • C. (ab*a)*
  • D. (b|ab*a)*

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Exercise 15: True or False Identities

  • Division: Senior

Which of these statements are true, for the alphabet a, b, c?

  • A. (ab)*a = a(ba)*
  • B. (a|b)* = a*|b*
  • C. a(b|c) = ab|ac
  • D. (a*)*b = a*b
  • E. ab* = (ab)*

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Exercise 16: Groups and Classes

  • Division: Senior

Which of these strings match the regular expression (ab)+c?[^abc]*?

  • A. ababx
  • B. abc
  • C. abcc
  • D. aba
  • E. c
  • F. abcdd

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Exercise 17: Full Pattern Checker

  • Challenge
  • Division: Senior

Extend your Pattern Checker to the extended syntax of Lesson 3. A pattern is now a line of items, and each item may be followed by one mark ?, + or *. An item is one of:

  • a single letter or digit, which matches that character
  • ., which matches any one character
  • a class in square brackets, which matches one character: [abc] matches any character listed; [^abc] matches any character not listed; and inside a class, x-y stands for every character from x to y, as in [a-d] or [A-Z0-9]

The input is the same as in the Pattern Checker: the pattern, then n, then n words, with - standing for the empty word. For each word, in order, print ACCEPT if it matches the pattern and REJECT if not.

Constraints

  • The pattern has between 1 and 30 characters. A class holds letters, digits and ranges x-y (with x before y), and may start with ^; it is never empty.
  • n is between 1 and 20.
  • Each word has between 0 and 20 letters (small or capital) and digits (written - when it has 0).

Sample Input

Hi?g+h+[^a-ceiou]
7
Highb
HigghhhC
Hihh
Hiihgh
Highd
HgggggghX
Hgh

Sample Output

REJECT
ACCEPT
REJECT
REJECT
ACCEPT
ACCEPT
REJECT

Two characters can be compared with <= just like numbers: "a" <= "c" is True.

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output line by line.

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

For parents and teachers: report a problem

Exercise 18: Hidden Pattern

  • Challenge
  • Division: Senior

How many strings of exactly 5 symbols, each symbol a or b, are described by the regular expression (a|b)*aba(a|b)*?

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: a number

For parents and teachers: report a problem

Back to Unit 11 — FSAs and Regular Expressions