Show Menu
Cheatography
  1. Home >
  2. Education >

Automata Theory Exam 2 Cheat Sheet (DRAFT) by

this is my exam study

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Pumping Lemma

if a langugae L ⊆ Σ* is regular, then there exists a constant n > 0 such that for any string z ∈ L, |z| ≥ n, z can be factorized as z= uvw with the following proper­ties:
i) |uv| ≥ n (loop is in the beginning)
ii) |v|≥ 1 (loop isn't empty)
iii) ∀ i ≥ 0, uvⁱw ∈ L
v can be repeated any number of times, and string is still in the language
"if L is regular(p) , then q is true" which implies if q is not true, then L is not regular
5 steps to prove languagae isn't regular given a language L ⊆ Σ*
1.) Pick an arbitrary constant n > 0
2.) choose a string z s.t. z ∈ L
3.) consider a factor­ization of z=uvw s.t. |uv| ≥ n and |v ≥ 1
4.) find an integer i s.t. z' = uvⁱw ∉ L
5.) conclude that L is not regular

Closure Properties of Regular languages: