SkipCaptcha
265
edits
Changes
Jump to navigation
Jump to search
Line 263:
Line 263: − + − Several examples appear in these lecture notes.+ Line 273:
Line 273: + + + + + + + + + + + + + + + + + + + + +
→Chomsky hierarchy: add context-sensitive example
X [non-terminal] Y -> X [anything] Y
X [non-terminal] Y -> X [anything] Y
where X and Y determine the context in which the [non-terminal] is transformed. Note that X and Y may each be terminals or non-terminals or [nothing].
where X and Y determine the context in which the [non-terminal] is transformed. Note that X and Y may each be terminals or non-terminals or [nothing]. When both X and Y are nothing there is no context and this reduces to a Level 2 or Level 3 grammar.
====Example====
====Example====
Taylor has provided several examples
<ref>{{cite web
<ref>{{cite web
| url = http://www.divms.uiowa.edu/~fleck/taylor.pdf
| url = http://www.divms.uiowa.edu/~fleck/taylor.pdf
| accessdate = 2012-04-26
| accessdate = 2012-04-26
}}</ref>
}}</ref>
and the following, inspired by his third example, is an extension of the original simple example to handle singulars and plurals:
''Sentence'' -> ''NounPhrase'' ''VerbPhrase'' # simple sentence structure
''NounPhrase'' -> ''Determiner'' ''Noun'' # simple phrase structure
''VerbPhrase'' -> ''Verb'' ''NounPhrase'' # simple phrase structure
#
''Noun'' -> ''SingularNoun'', ''PluralNoun'' # nouns can be singular or plural
#
''Determiner'' ''SingularNoun'' -> ''SingularDeterminer'' ''SingularNoun'' # determiner must agree with noun:
''Determiner'' ''PluralNoun'' -> ''PluralDeterminer'' ''PluralNoun'' #
#
''SingularNoun'' ''Verb'' -> ''SingularNoun'' ''SingularVerb'' # verb must agree with noun
''PluralNoun'' ''Verb'' -> ''PluralNoun'' ''PluralVerb'' #
#
''SingularDeterminer'' -> '''a''', '''the''' # singular determiners
''PluralDeterminer'' -> '''the''' # plural determiners
#
''SingularNoun'' -> '''boy''', '''sheep''', '''dog''' # singular nouns
''PluralNoun'' -> '''boys''', '''sheep''', '''dogs''' # plural nouns
#
''SingularVerb'' -> '''chases''', '''hears''', '''sees''' # singular verbs
''PluralVerb'' -> '''chase''', '''hear''', '''see''' # plural verbs
===Level 0===
===Level 0===