31 Jan 03:30 PM
CSCI 5100
0
s and 1
s01
s and 10
s.
0101
∉C0110
∈C∀A:∃p∈N:∃xyz∈A:|xyz|≥p⟹∀i∈N:xyiz∈A∧|y|>0∧|xy|≤p - That is, {xz,xyz,xyyz}∈A
y
# assume S as a list of states.
S : List[states]
x : str
y : str
z : str
assert(states(x + z) == S[:i] + S[j:])
assert(states(x + y + z) == S == S[:i]+S[i:j]+S[j:])
assert(states(x + y + y + z) == S[:i] + S[i:j] + S[i:j] + S[j:])
assert(states(x + y * 2 + z) == S[:i] + S[i:j] * 2 + S[j:])
# This can't run - it's infinite
assert(all((states(x+y*n+z) == A[:i]+A[i:j]*n+A[j:]) for n in count()))
\begin{aligned} &\forall A :\exists p \in \mathbb{N} : \\ &\exists xyz \in A : |xyz| \geq p \implies \\ &\forall i \in \mathbb{N} : xy^iz \in A \land \\ &|y| > 0 \land \\ &|xy| \leq p \end{aligned}
Proof
0
s and 1
s”