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

Voltage tripler and voltage quadrupler.., explan volage triper and voltage ...

explan volage triper and voltage quadrupler.

Explain two dimensional array, Explain two dimensional array In two dim...

Explain two dimensional array In two dimensional arrays, array is a pointer-to-pointer-to-data type.: at the first level, it points to a block of pointers, one for each row. Th

First-order inference rules, First-Order Inference Rules: Here now we ...

First-Order Inference Rules: Here now we have a clear definition of a first-order model is that we can define soundness for first-order inference rules in the same way such we

Payroll pc, Purpose: Payroll processing and storage for the client database...

Purpose: Payroll processing and storage for the client database (accessed from the Reception-PCover the network),word processing (reports etc.) and spreadsheets. Software: . • W

Array is a pointer to pointer to int, Array is a pointer-to-pointer-to-int:...

Array is a pointer-to-pointer-to-int: at the first level, it points to a block of pointers, one for each row. That first-level pointer is the first one we allocate; it has nrows e

What is closed system, Closed System: It's isolated from environment influ...

Closed System: It's isolated from environment influences. It operates on factors within System itself. It is also described as a System which involves a feedback loop, a control e

What is reentrant tasks and functions, What is reentrant tasks and function...

What is reentrant tasks and functions Tasks and functions without optional keyword automatic are static , with all declared items being statically allocated. These items will b

Using the memory map design an absolute decoding circuit, Using the memory ...

Using the memory map below; design an absolute decoding circuit. The technique is to spot the differences between the start and stop of each device. The Ram chip has the follow

How do you ensure that our records are scanned accurately, How do you ensur...

How do you ensure that our records are scanned accurately? Not only do we have a highly trained and capable staff, we also have quality controls in place to make sure your reco

Show the internet protocols, A communication protocol is an agreement which...

A communication protocol is an agreement which specifies a common language two computers use to exchange messages. For instance, a protocol specifies exact format and meaning of ev

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages