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 artificial intelligence language processing, Artificial intelligenc...

Artificial intelligence language processing (AILP) is a field of computer science and linguistics concerned with the interactions among computers and human (natural) languages; it

Find traffic offered and lost, Discuss grade of service. During busy hour, ...

Discuss grade of service. During busy hour, 1500 calls were offered to a group of trunks and 8 calls were lost. The average call duration was 120 seconds. Calculate the traffic off

The current image in gimp, How do we merge an image from a file to the curr...

How do we merge an image from a file to the current image in GIMP? Ans) Use "File then Open as Layers" menu command or just take the file to a window and drop it there. The file w

Determine the framed data including a parity bit, Determine the Framed data...

Determine the Framed data including a parity bit   For illustration when even parity is chosen, parity bit is transmitted with a value of 0 if the number of preceding

Keyboard status word generator, Q.  Write short note on Interfacing Keyboar...

Q.  Write short note on Interfacing Keyboard, giving block diagram. Why do we need to introduce circuitry called Keyboard Status Word Generator?

Explain keyboard input and video output, Q. Explain Keyboard Input and Vide...

Q. Explain Keyboard Input and Video output ? A Keystroke read from keyboard is termed as a console input and a character displayed on the video screen is known as a console out

Example on distribution of data, Q. Example on Distribution of Data? !H...

Q. Example on Distribution of Data? !HPF$ PROCESSORS P1(4) !HPF$ TEMPLATE T1(18) !HPF$ DISTRIBUTE T1(BLOCK) ONTO P1  Consequently of these instructions distribution of

Define secondary memory, Define secondary memory. This memory holds tho...

Define secondary memory. This memory holds those pages that are not present in main memory. The secondary memory is usually a high speed disk. It is known as the swap evice, an

Learning weights in perceptrons, Learning Weights in Perceptrons: Furt...

Learning Weights in Perceptrons: Furthermore details are we will look at the learning method for weights in multi-layer networks next lecture. Thus the following description o

Design 4 to 1 multiplexer with strobe input using nand gates, Design a 4 : ...

Design a 4 : 1 multiplexer with strobe input using NAND gates. Ans. Design of 4 : 1 multiplexer with strobe input using NAND gates.

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