随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0


Comlement and Intersection of Regular Language


Subjects to be Learned

  • Complement of Regular Language
  • Complement of DFA
  • Intersection of Regular Languages



Let M = < Q , clip_image001, q0 , clip_image002, A > be a DFA that accepts a language L. Then a DFA that accepts the complement of L, i.e. clip_image001* - L, can be obtained by swapping its accepting states with its non-accepting states, that is Mc = < Q , clip_image001, q0 , clip_image002, Q - A > is a DFA that accepts clip_image001* - L .

For example the following DFA accepts the language a+ over clip_image001= { a , b }.


A DFA that accepts its complement is obtained from the above DFA by changing all single circles to double circles and vice versa as shown below.


Remark 1: If we have NFA rather than DFA, we must first convert it to DFA before swapping states to get its complement.

Remark 2: Since a language is regular if and only if it is accepted by some NFA, the complement of a regular language is also regular.

Intersection of Regular Languages

Langauges are sets. Therefore all the properties of sets are inherited by languages. In particular De Morgan's law also applies to languages. By Remark 2 above, if L1 and L2 are regular languages, then their complements are regular languages. Since L1 clip_image005L2 = clip_image006by De Morgan's law, L1 clip_image005L2 is regular.

Thus summing all this up we can say that the set of regular languages over an alphabet is closed with respect to union, intersection, difference, concatenation and Kleene star operations.

Test Your Understanding of Complemnent and Intersection of FAs

Indicate which of the following statements are correct and which are not.
Click True or Fals , then Submit.

posted on 2009-11-05 12:14 肥仔 阅读(1196) 评论(0)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言

【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理