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

4 bit comparator, how to breadboARD THE 4 BIT COMPARATOR

how to breadboARD THE 4 BIT COMPARATOR

What are the advantages of having e-commerce over extranets, What are the a...

What are the advantages of having e-commerce over extranets?     Extranets are about " joining up" the supply chain-suppliers, resellers, distributors, customers, etc.-enabling

What are the advantages of hierarchical networks, What are the advantages o...

What are the advantages of Hierarchical Networks? Hierarchical networks are able of handling heavy traffic where needed, and at similar time use minimal number of trunk groups

What do you mean by execution unit, Q. What do you mean by Execution Unit? ...

Q. What do you mean by Execution Unit? Execution unit performs all ALU operations. Execution unit of 8086 is of 16 bits. It also contains the control unit that instructs bus in

Create the website home page, Now when a site structure is set up for stori...

Now when a site structure is set up for storing pages and assets for Compass site, you'll create the first page-a home page for the site. As you build this page, you will add text,

Describe attributes and properties of system, System Analysis & Design ...

System Analysis & Design 1. Describe attributes, properties, and characteristics of system. 2. What do you mean by Organizational Aspects of System Life Cycles? Explain.

First-order models -artificial intelligence, First-Order Models - Artificia...

First-Order Models - Artificial intelligence: We proposed first-order logic like good knowledge representation language rather than propositional logic because it is more expre

Explain about operand address calculation, Q. Explain about Operand Address...

Q. Explain about Operand Address Calculation? In actual machines effective address can be a register address, memory or I/O port address. Register reference instructions for ex

What is the sequence in which resources may be utilized, What is the sequen...

What is the sequence in which resources may be utilized?  Under normal mode of operation, a process might be utilize a resource in the following sequence:  • Request: If the

Explain the working of static ram - computer memory, Explain the working of...

Explain the working of Static RAM - Computer Memory? SRAM devices tender extremely fast access times (approximately four times faster than DRAM) but are much more expensive to

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