4.1 Inexpressibility

Question 1

How do we know there is a loop in the following run of a finite automata

Answer 1

Revisits same state twice (2)

Question 2

Given the following string with some run states highlighted in green, give examples of another string that could be accepted

Answer 2

We can imagine the automaton choosing to go around that loop any number of times as part of accepting a word (including zero times).

Question 3

Given word aaaaba and knowing the automata contains 5 states, deduce another words that might be accepted.

Answer 3

There must be a loop - don’t know how many states for loop. Say p states. Initial state = 1, then first a = 2 … last contig a = 5

Question 4

What is the No Matched Parentheses Theorem

Answer 4

a = opening parenthesis or html tag and b is closing.

Question 5

How to prove the No Matched Parentheses Theorem

Answer 5

• Proof by contradiction
• Assume is a regular language / finite automata
• Assume k states
• Try to prove a^k b^k
• Show there is a loop
• Then show a^k+p b^k also works
• Violates the theorem