Explain chomsky classification of languages, Computer Engineering

Assignment Help:

Explain chomsky classification of languages with suitable examples

Ans: Any language is appropriate for communication provided the syntax & semantic of the language is termed to the participating sides.  It is made feasible by forcing a standard on the way to create sentences from words of that language. This standard is forced by a set of rules. This set of rules is known as grammar of the language. As per to the Chomsky classification, a grammar G = (N, ∑, P, S) is known as Type 0: if there is no restriction on the production rules that is in α→β, in which α, β∈ (N ∪ ∑)*. This type of grammar is as well called an unrestricted grammar and language is known as free language.  

Type 1:  if in eash production α→β of P, α,  β ∈ (N ∪ ∑)* and |α|  ≤ |β|. Here |α| and |β| denote number of symbols in string α and β correspondingly. This type of grammar is as well called a context sensitive grammar (or CSG) and language is known as context sensitive.

Type 2:  if in each production α→β of P, α ∈ N and β ∈ (N ∪ ∑)*. Here α is a single non-terminal symbol. This kind of grammar is as well known as a context free grammar (or CFG) and language is called context free.

Type 3:  if in each production α→β of P, α ∈ N and β ∈ (N ∪ ∑)*. Here α is a single non-terminal symbol and β may contain at the most one non-terminal symbol and one or more terminal symbols. The non-terminal symbol appearing in β should be the extreme right symbol.

This kind of grammar is as well called a right linear grammar or regular grammar (or RG) and the corresponding language is known as regular language.


Related Discussions:- Explain chomsky classification of languages

Explain the storage class extern, Explain The Storage Class extern The...

Explain The Storage Class extern The Storage Class extern : One method of transmitting information across blocks and functions is to use external variables. When a variable is

Where do you set automatic correlation options, Automatic correlation from ...

Automatic correlation from web point of sight can be set in recording options and correlation tab. Here we can enable correlation for the whole script and choose either issue onlin

Explain about instruction register and flags, Q. Explain about Instruction ...

Q. Explain about Instruction Register and Flags? The Instruction Register: It comprises the operation code (opcode) and addressing mode bits of the instruction. It assists in

C++, pebble merchant

pebble merchant

Priority interrupt and synchronous bus, What is a Priority Interrupt? A...

What is a Priority Interrupt? Ans: A priority interrupt is a type of interrupt that establishes a priority over the many sources to determine which condition is to be serviced

Operations of a scientific calculator, A program is to be developed to simu...

A program is to be developed to simulate the operations of a scientific calculator. List the facilities to be provided by this calculator. Analyze this using a DFD 0- level and 1-

What is an operating system, What is an operating system? An operating...

What is an operating system? An operating system is system software which provides interface between hardware and user. The operating system gives the means for the proper uti

Define about hyper-threading technology, Q. Define about Hyper-threading te...

Q. Define about Hyper-threading technology? Hyper-threading technology enables a single microprocessor to behave as two separate threaded processors to operating system and app

Explain working of supercomputer, Q. Explain working of Supercomputer? ...

Q. Explain working of Supercomputer? Supercomputers, capable of executing in excess of one billion floating-point operations per second (FLOPS), are very powerful, extremely hi

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