[PDF] The Chomsky Hierarchy Chomsky introduced the hierarchy of

View - Download The Chomsky Hierarchy

Previous PDF

Next PDF

The Chomsky Hierarchy

There are other types of grammars.

Regular Grammars

We noted that every regular language has a CFG.

In fact, a regular language (without") can be

generated by a special form:

Aregular grammaris one where every pro-

duction is of the formA!bCorA!a (whereaandbare some terminals andC some variable).

Goddard 8a: 2

Regular Languages have Regular Grammars

Theorem.Every regular language is generated

by a regular grammar.PROOF. Idea: produce a grammar such that a derivation mimics the operation of the automa- ton. Every stage of derivation will have a single vari- able that is the state of the FA.

Goddard 8a: 3

Construction of Regular Grammar

Start with DFA for the language. Introduce one

variable for each state.

For each transition, add a production:

if(A;x) =B, then add productionA!xB.

For each transition ending at an accept state,

add a further production: ifBis accept state in above, then also add productionA!x.

The start variable is the start state.

Goddard 8a: 4

Example

Consider RE(11+00)11.

Goddard 8a: 5

Example

Consider RE(11+00)11. Here is NFA:

S A B C 1 0 0 0 1 1

Goddard 8a: 6

Example

Consider RE(11+00)11. Here is NFA:

S A B C 1 0 0 0 1

1This yields the following regular grammar:

S!0Cj1A

A!1Bj1

B!0Cj1A

C!0S

Goddard 8a: 7

Practice

Draw an FA, and from there write down a regu-

lar grammar, for the language given by the RE 0 0 11.

Goddard 8a: 8

Solution to Practice

S A B 0 0 1 1S!0A

A!0Aj1Bj1

B!1Bj1

Goddard 8a: 9

Unrestricted & Context-Sensitive Grammars

Inunrestricted grammars, productions have

formu!vwhereuandvare any strings of terminals and/or variables.

Incontext-sensitive grammars, productions

have formxAz!xyzwherex,yandzare strings of terminals and/or variables, andAis a vari- able.

Goddard 8a: 10

Context-Sensitive Example

A context-sensitive grammar for0n1n2nis not

obvious!

S!0BS2j012

B0!0B B1!11 (Try to derive000111222.)

Goddard 8a: 11

The Chomsky Hierarchy

Chomsky introduced the hierarchy of grammars

in his study of natural languages. 0.

Unr estrictedgrammars.

1.

Context-sensitive grammars.

2.

Context-fr eegrammars.

3.

Regular grammars.

We have seen that regular grammars are ac-

cepted by FAs, and that CFGs are accepted by

PDAs. We will see later machines for the other

two types.

Goddard 8a: 12

Simplifying CFGs: Usable & Nullable Variables

A variable isusableif it generates some string

of terminals. A variable isnullableif it gener- ates the empty string.

Example: In the following,AandBare usable

but onlyBis nullable.

A!0Aj1Bj2C

B!0Bj"

C!1C

Goddard 8a: 13

Algorithm for Nullable Variables

Identification of nullable variables.Initialize

all variables as not-nullable.

Repeat:

go through all productions, and if any has

RHS empty or all entries nullable,

then mark the LHS variable as nullable; Until no increase in the set of nullable variables.A similar procedure can be used to determine the usable variables.

Goddard 8a: 14

Summary

A regular grammar is one where every produc-

tion has the formA!bCorA!a. The Chom- sky hierarchy also includes context-sensitive grammars and unrestricted grammars.

Goddard 8a: 15

quotesdbs_dbs14.pdfusesText_20

[PDF] chomsky's contribution to linguistics pdf

[PDF] choose the best concluding sentence worksheet

[PDF] choosing features for clustering

[PDF] chromatic harmonica pdf

[PDF] chromatic harmonica scales

[PDF] chrome browser extension vulnerabilities

[PDF] chrome cleanup tool

[PDF] chrome curtain pole crystal finials

[PDF] chrome curtain pole glass finials

[PDF] chrome extension developer mode

[PDF] chrome extension template

[PDF] chrome extension tutorial 2018

[PDF] chrome extension tutorial 2020

[PDF] chrome extension tutorial for beginners

[PDF] chrome extension tutorial popup