2-Chomsky hierarchy of languages.ppt

Brief

1. Chomsky hierarchy of languages

2. AccordingtoChomskyhierarchy,grammarisdividedinto4typesasfollows:
1.Type0isknownasunrestrictedgrammar.
2.Type1isknownascontext-sensitivegrammar.
3.Type2isknownasacontext-freegrammar.
4.Type3RegularGrammar.
Type0:UnrestrictedGrammar:
Type-0grammarsincludeallformalgrammar.Type0grammarlanguagesare
recognizedbyturingmachine.TheselanguagesarealsoknownastheRecursively
Enumerablelanguages.
GrammarProductionintheformofwhere
\alpha
V:VariablesT
:Terminals.
is(V+T)*V(V+T)*
is(V+T)*.
Intype0theremustbeatleastonevariableontheLeftsideof
production.Forexample:
Sab-->baA-->S
Here,VariablesareS,A,andTerminalsa,b.
Type1:Context-SensitiveGrammar

3. Type-1grammarsgeneratecontext-sensitivelanguages.Thelanguagegeneratedby
thegrammarisrecognizedbytheLinearBoundAutomata
InType1
FirstofallType1grammarshouldbeType0.
GrammarProductionintheformof
|\alpha|<=|\beta|
Thatisthecountofsymbolin
Alsoβ ∈ (V+T)
+
i.e.β cannotbeε
islessthanorequalto
ForExample:
S-->AB
AB-->abcB-->b
Type2:Context-FreeGrammar:Type-2grammarsgeneratecontext-free
languages.ThelanguagegeneratedbythegrammarisrecognizedbyaPushdown
automata.InType2:
Firstofall,itshouldbeType1.
Theleft-handsideofproductioncanhaveonlyonevariableandthereis
norestrictionon
|=1.|\alpha
Forexample:
S-->AB
A.-->a
B.-->b
Type3:RegularGrammar:Type-3grammarsgenerateregularlanguages.These
languagesareexactlyalllanguagesthatcanbeacceptedbyafinite-state
automaton.Type3isthemostrestrictedformofgrammar.
Type3shouldbeinthegivenformonly:
V-->VT/T
(or)
V-->TV/T
Forexample:
S-->a
(left-regulargrammar)
(right-regulargrammar)
Theaboveformiscalledstrictlyregulargrammar.

4. Thereisanotherformofregulargrammarcalledextendedregulargrammar.Inthis
form:
V-->VT*/T*.
(or)
V-->T*V/T*
Forexample:
S-->ab.
(extendedleft-regulargrammar)
(extendedright-regulargrammar)