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

Dynamic programming, The fi rst task will involve doing a little background...

The fi rst task will involve doing a little background reading on Dynamic Programming to get up to speed. The second task is to write the code: Search Space Write a function whi

Basic need of random access memory, Q. Basic need of Random Access Memory? ...

Q. Basic need of Random Access Memory? Main memory is Random access memory. It is generally organised as words of fixed length. Length of a word is termed as word length. Every

What is efi framework, The Extensible Firmware Interface (EFI) is a specifi...

The Extensible Firmware Interface (EFI) is a specification that defines a software interface among an operating system and platform firmware. EFI is intended as a significantly imp

Constructor, what is meant by private copy constructor

what is meant by private copy constructor

Explain lan topologies, Explain LAN Topologies and its basic topologies. ...

Explain LAN Topologies and its basic topologies. LAN Topologies: Network topology is a physical schematic that shows interconnection of the various users. There are four fund

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

Search-based tools in parallel computers, The search-based tools initially ...

The search-based tools initially recognize problem and afterwards suitably give advice on how to correct it.  AT Expert from Cray Research is one of the tools being employed for

What is ''LRU'' page replacement policy, 'LRU' page replacement policy is ?...

'LRU' page replacement policy is ? Ans. Least Recently Used.

Explain about the term- reports, Explain about the term- Reports Repor...

Explain about the term- Reports Reports are produced as a result of questions like "how many times has a type of car broken down" or "which cities have the highest house price

Symbolic reasoning, An expert system also represents knowledge symbolica...

An expert system also represents knowledge symbolically as sets of symbols that stand for problem concepts. In AI jargon symbol is a string of characters that stands for

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