Alex Rivera | Logout

The difference between Chomsky type 3 and Chomsky type 2 grammar

Asked 2012-07-18T19:57:28.607
21

I'm having trouble articulating the difference between Chomsky type 2 (context free languages) and Chomsky type 3 (Regular languages).

Can someone out there give me an answer in plain English? I'm having trouble understanding the whole hierarchy thing.

Edit
Report

1 Answer

6

The wikipedia page has a good picture and bullet points.

Roughly, the underlying machine that can describe a regular language does not need memory. It runs as a statemachine (DFA/NFA) on the input. Regular languages can also be expressed with regular expressions.

A language with the "next" level of complexity added to it is a context free language. The underlying machine describing this kind of language will need some memory to be able to represent the languages that are context free and not regular. Note that adding memory to your machine makes it a little more powerful, so it can still express languages (e.g. regular languages) that didn't need the memory to begin with. The underlying machine is typically a push-down automaton.

answered 2012-07-18T20:15:49.430

Your Answer