Explain their characteristics and limitations of grammar, Computer Engineering

Assignment Help:

Identify the different classes of grammar. Explain their characteristics and limitations.

As proposed through Noam Chomsky that Chomsky hierarchy contains the subsequent levels:

  • Type-0 grammars (unrestricted grammars) contain all formal grammars. They produce exactly all languages which can be recognized by a Turing machine. The language which is recognized by a Turing machine is termed as all the strings on which this halts. These languages are also termed as the recursively enumerable languages.
  • Type-1 grammars (context-sensitive grammars) produce the context- sensitive languages. These grammars include rules of the form αAβ → αγβ along with A a non terminal and α, β and γ strings of terminals and non-terminals. All strings α and β may be empty, but γ should be nonempty. The rule S → ε is permitted if S does not show on the right side of any rule. The languages described through these grammars are exactly all languages which can be recognized through a non-deterministic
  • Type-2 grammars (context-free grammars) make the context-free languages. These are defined through rules of the form A → γ along with A a non terminal and γ a string of terminals and non-terminals. Such languages are exactly all languages which can be recognized through a non-deterministic push-down automation. Context free languages are the theoretical basis for the syntax of main programming languages.
  • Type-3 grammars (regular grammars) produce the regular languages. A grammar restricts its rules to a single non-terminal on the left-hand side and a right-hand side having a single terminal, possibly followed through a single non terminal. Also the rule S → ε is here allowed if S does not show on the right side of any rule. Such languages are exactly all languages that can be decided through a finite state automaton. Moreover, this family of formal languages can be acquired by regular expressions. Regular languages are usually used to explain search patterns and the lexical structure of programming languages.

Related Discussions:- Explain their characteristics and limitations of grammar

C programming, There is a pebble merchant. He sells the pebbles, that are u...

There is a pebble merchant. He sells the pebbles, that are used for shining the floor. His main duty is to take the length of the room’s sides. But he sometimes mistakes doing that

Synchronous, What are differences between Synchronous, Asynchronous and I s...

What are differences between Synchronous, Asynchronous and I synchronous communication? Sending data encoded in your signal needs that the sender and receiver are both by using

Placement algorithm - process allocation, Placement algorithm - computer ar...

Placement algorithm - computer architecture: Different strategies can be taken as to how space is allocated to processes: First fit : Allocate the first hole that is la

What are different types of log records, What are different types of Log re...

What are different types of Log records? V1 and V2.  V1 must be processed before V2.  But, we can have more than single V2 logs

What is the scope of public members in all classes, What is the Scope of pu...

What is the Scope of public/private/friend/protected/protected friend?    Scope of public/private/friend/protected/protected friend. Visual Basic/Visual C# Public/pub

Interaction design, This unit introduces the most important ID terminology,...

This unit introduces the most important ID terminology, explains why ID is important, and gives a description of the main ID activities and the characteristics of the ID process. I

What are the different phases of consumer mercantile model, What are the di...

What are the different phases of consumer mercantile model? There are three different phase of consumer mercantile model like listed as in below: • Pre-purchase interaction

Two services that are used to deal with communication, Explain about the tw...

Explain about the two services that are used to deal with communication. Message Service: Used by the application servers to change short internal messages, all system commu

Describe about general-purpose microprocessor, Q. Describe about general-pu...

Q. Describe about general-purpose microprocessor? Keeping rapidity with electronics as more and more components were fabricated on a single chip fewer chips were required to ma

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd