Lecture 11

October 25th, Friday (08:30-10:30)

Properties of regular languages

• Test on the intersection between regular and non regular languages
• Superset and subset operators and language properties

Exercises

• Prove that the following languages are not regular (Exercise 1.4 in the Exercise collection):
  • \( L_{=} = \{ a^{n} b^{n} \; | \; n \geq 1 \} \)
  • \( L_{>} = \{ a^{n} b^{m} \; | \; n, m \geq 1, \; n > m \} \)
  • \( L_{<} = \{ a^{n} b^{m} \; | \; n, m \geq 1, \; n < m \} \) <%7%6%>
  • \( L_{\neq} = \{ a^{n} b^{m} \; | \; n,m \geq 1, \; n \neq m \} \)

  References

  • Hopcroft et al., chapter 4