SkipCaptcha
265
edits
Changes
→Level 1: add a few examples
A limitation/feature of both regular grammars and context-free grammars is that the left-hand side of any rule is always a single non-terminal item, so any transformation is applied regardless of the context in which that non-terminal item appears. A simple example which depends on context is the use of singular and plural nouns and verbs in English. We say: '''the man runs''' or '''the men run''', but neither of '''the man run''' nor '''the men runs'''. Which form of verb to use depends on the noun, i.e. there is a context dependency.
A limitation/feature of both regular grammars and context-free grammars is that the left-hand side of any rule is always a single non-terminal item, so any transformation is applied regardless of the context in which that non-terminal item appears. A simple example which depends on context is the use of singular and plural nouns and verbs in English. We say: '''the man runs''' or '''the men run''', but neither of '''the man run''' nor '''the men runs'''. Which form of verb to use depends on the noun, i.e. there is a context dependency.
===Level 1===
===Level 1: context-sensitive grammar===
For context-sensitive grammars the left-hand side of a rule may indicate the context in which that rule applies, so that the same non-terminal item may be transformed in different ways depending on the context in which it appears.
For context-sensitive grammars the left-hand side of a rule may indicate the context in which that rule applies, so that the same non-terminal item may be transformed in different ways depending on the context in which it appears.
| 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:
and the following, inspired by his third example, is an extension of the original simple example above to handle singulars and plurals:
''Sentence'' -> ''NounPhrase'' ''VerbPhrase'' # simple sentence structure
''Sentence'' -> ''NounPhrase'' ''VerbPhrase'' # simple sentence structure
''Noun'' -> ''SingularNoun'', ''PluralNoun'' # nouns can be singular or plural
''Noun'' -> ''SingularNoun'', ''PluralNoun'' # nouns can be singular or plural
#
#
''Determiner'' ''SingularNoun'' -> ''SingularDeterminer'' ''SingularNoun'' # determiner must agree with noun:
''Determiner'' ''SingularNoun'' -> ''SingularDeterminer'' ''SingularNoun'' # context-sensitive:
''Determiner'' ''PluralNoun'' -> ''PluralDeterminer'' ''PluralNoun'' #
''Determiner'' ''PluralNoun'' -> ''PluralDeterminer'' ''PluralNoun'' # determiner must agree with noun
#
#
''SingularNoun'' ''Verb'' -> ''SingularNoun'' ''SingularVerb'' # verb must agree with noun
''SingularNoun'' ''Verb'' -> ''SingularNoun'' ''SingularVerb'' # context-sensitive:
''PluralNoun'' ''Verb'' -> ''PluralNoun'' ''PluralVerb'' #
''PluralNoun'' ''Verb'' -> ''PluralNoun'' ''PluralVerb'' # verb must agree with noun
#
#
''SingularDeterminer'' -> '''a''', '''the''' # singular determiners
''SingularDeterminer'' -> '''a''', '''the''' # singular determiners
''SingularVerb'' -> '''chases''', '''hears''', '''sees''' # singular verbs
''SingularVerb'' -> '''chases''', '''hears''', '''sees''' # singular verbs
''PluralVerb'' -> '''chase''', '''hear''', '''see''' # plural verbs
''PluralVerb'' -> '''chase''', '''hear''', '''see''' # plural verbs
The above grammar can generate sentences such as: '''a boy chases a dog''', '''the boys chase a dog''', etc. Because some words have the same form in both singular and plural, it can also generate meaningful (and grammatically-correct) sentences such as: '''the sheep sees the dog''', '''the sheep see the dog'''.
But the above grammar can NOT generate sentences such as: '''a boys chases the sheep''', since this would violate the context-sensitive rules.
===Level 0===
===Level 0===