A language is called regular if it is accepted by some DFA

• Is the empty set regular?
  • Yes, we can simply have our start state be a final state
• Is the set of all strings over some fixed alphabet regular?
  • Yes, we can have one state which is the start state, final state, and all letters transition back into the state
• Is every language regular?
  • The number of languages is uncountably infinite
    • $2^{\sum^*}$
  • The number of DFA’s we can have is countably infinite as we can only have a finite set of states within each DFA
  • Each DFA is only capable of accepting one language
  • Thus every language cannot be regular. $2^{\sum ^*} >>$ number of DFA’s

🔪 Operations on languages

Any set operation can be applied to languages as they are just a set of strings.

There are also some specific operations.

Unary operations

• Complementation
• Reversal
• Truncation

Binary operations

• Union
• Intersection
• Concatenation

🌂 Closed operations

We say regular languages are closed under some operation if we can take a language that is regular, apply the operation to it, and be left with another regular language.

Complementation

If we have a DFA $M$ which accepts a language $L$, we can create a DFA to accept $\bar L$, the complement:

If we have $M=(Q, \sum, F, \delta)$ then $M'=(Q, \sum, Q \setminus F, \delta)$.