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

What is random access memory, Q. What is Random Access Memory? We will ...

Q. What is Random Access Memory? We will discuss RAM as an example of sequential circuit. A memory unit is a collection of storage cells or flip flops along with associated cir

What is expansion swap, What is Expansion swap? At the time when any pr...

What is Expansion swap? At the time when any process needs more memory than it is currently allocated, the Kernel performs Expansion swap. To do this Kernel reserves enough spa

What are the 3 segments of the default route, What are the 3 segments of th...

What are the 3 segments of the default route, that is there in an ASP.NET MVC application? Ans)  Segment 1st - Controller Name Segment 2nd - Action Method Name Segment 3r

Illustrate the accumulator architecture, Accumulator Architecture: An accu...

Accumulator Architecture: An accumulator is anespecially designated register which supplies one instruction operand and receives result. Instructions in such machines are usually

What are the basic components of an expert system, Q. What are the basic co...

Q. What are the basic components of an expert system? ANSWER: There are three components of components: Information, people, and IT components. Information kinds are domain exp

Show the responsibilities of session layer, Q. Show the Responsibilities of...

Q. Show the Responsibilities of session layer? Session layer: Main functions of this layer are to establish, synchronize and maintain the interaction between two communicatio

Develop a calculator in masm, Assignment:  develop a calculator in MASM. ...

Assignment:  develop a calculator in MASM. Text chapters covered:  1 through 4, 5.4, 5.5, 6.3, 7.4 You will develop a "calculator" algorithm in MASM using reverse-polish nota

Soundness - artificial intelligence, Soundness - artificial intelligence: ...

Soundness - artificial intelligence: You may see in some application domains-for example automated theorem proving - that your search is "sound and complete". The soundness in

Define intranet, Intranet : An Intranet is a type of information system...

Intranet : An Intranet is a type of information system that facilitates communication within the organizations between widely dispersed departments, divisions, and regional loc

Example of ann - artificial intelligence, Example of ANN - artificial intel...

Example of ANN - artificial intelligence: ANNs look like this:   Notice that the x, w, z and y represent actual valued weights and that every the edges in this graph

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