Understanding Chomsky Hierarchy in Language Theory
Explore Chomsky Hierarchy in language theory, including different types of languages, grammars, and automata. Learn how to prove if a language is regular, context-free, recursive, or recursively enumerable. Understand the closure properties of regular, context-free, recursive, and recursively enumerable languages under various operations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Chomsky Hierarchy Language Operations and Properties
You dont have to know this line The Chomsky Hierarchy Type Language Grammar Automaton 0 Recursively Enumerable Unrestricted DTM - NTM 1 Context Sensitive Context Sensitive Linearly Bounded Automaton 2 Context Free Context Free NPDA 3 Regular Right Linear, Left Linear DFA, NFA Type Type Type Type 3 2 1 0
The Chomsky Hierarchy Recursively Enumerable Languages {<M>, H(<M>)} Recursive Languages {anbncn, n 0} Context Free Languages {anbn , n 0} Regular Languages {ambn , m,n 0}
Regular Languages To prove that a language is regular: Find a DFA (NFA, NFA ) that recognizes it. Find a regular expression that represents is. Find a (right or left) linear grammar that generates it.
Context Free Languages To prove that a language is context free: Find a PDA that recognizes it. Find a context free grammar that generates it.
Recursive Languages To prove that a language is recursive you must find a Turing Machine that decides membership in the language: If the string is in the language then the machine should accept. If the string is not in the language then the machine should reject. The machine should never loop (on any input).
Recursively Enumerable Language To prove that a language is recursively enumerable: Find a Turing Machine that recognizes it: if the string is in the language the machine should accept. if the string is not in the language the machine should loop or reject. Give an unrestricted grammar that represents it (you won t be asked to do that )
Closure under operations Regular Languages are closed under: Union, Concatenation, Star, Intersection and Complement Context Free Languages are closed under: Union, Concatenation, Star. They are not closed under: Intersection, Complement. Recursive Languages are closed under: Union, Concatenation, Star, Intersection, Complement Recursively Enumerable Languages are closed under: Union, Concatenation, Star, Intersection. They are not closed under Complement.
Properties mixing languages If a language L1is context free and a language L2is regular then the intersection of L1and L2 is context free. Given the fact that there is a PDA M1recognizing L1 and a DFA M2recognizing L2we can create a PDA M for L1 L2. M is going to simulate the run of M1 while keeping track of transitions of M2. This idea is quite similar to the proof that regular languages are closed under intersection, we only have to take additional care about the stack of M1.
Properties mixing languages If a language L and its complement Lcare both recursively enumerable then the language L is recursive. Both L and its complement have TMs M and M that recognize them. To decide whether x is in L: Run both machines M and M in parallel. One of them will eventually halt: - If M halts accept. - If M halts reject.
