Scribd
Upload
6 views12 pages

Non-Regular Languages and Closure Properties

The document discusses the proof that certain languages, such as L={anbn : n >= 0}, the Balanced Parenthesis Language, and the Even Palindrome language, are not regular. It also outlines closure properties of regular languages, including closure under complementation, intersection, and difference. Additionally, it mentions the equivalence and minimization of automata using a table filling method.

Uploaded by

pranavkeshav4
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views12 pages

Non-Regular Languages and Closure Properties

The document discusses the proof that certain languages, such as L={anbn : n >= 0}, the Balanced Parenthesis Language, and the Even Palindrome language, are not regular. It also outlines closure properties of regular languages, including closure under complementation, intersection, and difference. Additionally, it mentions the equivalence and minimization of automata using a table filling method.

Uploaded by

pranavkeshav4
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Proving Languages Not to Be Regular

The Pumping Lemma/Theorem for Regular languages


Ex 1: Show that L={ anbn : n >= 0}is not regular .

So L= anbn is not regular.

Ex 2: The Balanced Parenthesis Language is Not Regular


Let L be Bal = {w∈{ ), ( }* : the parentheses are balanced}.

So, it is not Regular.

Ex 3: The Even Palindrome language is Not Regular


Let L be PalEven = {wwR: w ∈{a,b}*}.

So L = PalEven is not regular.


Closure Properties of Regular Languages

Closure Under Complementation


1. Convert the regular expression to an ℇ-NFA
2. Convert that ℇ-NFA to a DFA by the subset construction
3. Complement the accepting states of that DFA
4. Turn the complement DFA back into a regular expression using the subset construction method
Closure Under Intersection
Theorem: If L and M are regular languages, then so is L ∩ M
Closure Under Difference
There is a fourth operation that is often applied to sets and is related to the boolean operations: set
difference. In terms of languages, L-M is the difference of L and M. It is the set of strings that are in
language L but not in language M. The regular languages are also closed under this operation.
Equivalence and Minimization of Automata - table filling method

You might also like