regular languages

• REGULAR LANGUAGES

  Regular Languages (RLs) are the ones that can be expressed by DFAs, NFAs, ε-NFAs, or REs

  
• PIGENHOLE PRINCIPLE

  If there are k + 1 pigeons and k pigeonholes, there must be 2 pigeons in the same pigeonhole.

  For an automaton with k states, this means that, after reading the k +1 preffixes of a string, it must have passed twice in the same state.

  
• (NON-) REGULAR LANGUAGES

  
• (NON-) REGULAR LANGUAGES

  Consider a DFA with n states

  Passing only 1x in each state, the length of any string w recognized by the DFA is: |w| ≤ n - 1

  The maximum length passing only 1x in each state is n - 1 and correspond to (image below)

  To recognize strings w with |w| ≥ n, at least one state must be passed more than 1x

  
• (NON-) REGULAR LANGUAGES

  Infinite RLs must have at least one state repeating:

  
• (NON-) REGULAR LANGUAGES

  Infinite RLs must have at least one state repeating: