Explanation Productions in a phrase-structure grammar is given, you need to identify type of grammar this is in the Chomsky classification scheme. Follow the below algorithm to generate the productions and identify type of grammar. Algorithm Input: N ← standard input, productions ← { }, Count ← 0 While count < N Take input LHS and RHS of production Add this production in grammar Count = Count + 1 If isType3 (productions) Print (“Type 3 Grammar.”) Else if isType2 (productions) Print (“Type 2 Grammar.”) Else if isType1 (productions) Print (“Type 1 Grammar.”) Else if isType0 (productions) Print (“Type 0 Grammar.”) Else Print (“Grammar does not belongs from Chomsky classification scheme.”) Output: Type of grammar in the Chomsky classification scheme. Where N = Number of productions. Count = number of productions already generated A phrase-structure grammar G = ( V , T , S , P ) consists of a vocabulary V, a subset Tof V consisting of terminal symbols, a start symbol S from V, and a finite set of productions P. The set V - T is denoted by N. Elements of N are called nonterminal symbols.Every production in P must contain at least one nonterminal on its left side. A production is represented as α → β where α derives β According to Chomsky classification scheme there are four types of grammar. Type 0 grammar or unrestricted grammar Type 1 grammar or context sensitive grammar Type 2 grammar or context free grammar Type 3 grammar or regular grammar T y p e 3 ⊆ T y p e 2 ⊆ T y p e 1 ⊆ T y p e 0 isType3 ( ) function is checking whether grammar is of type 3 or not, a grammar is type 3 if all of its production α → β follow following rules. α is single non-terminal i.e. α ∈ N β ∈ T * N Or N T * i.e. grammar is either left linear or right linear but not both at same time except when T is null or β itself is null. * Represents kleeneclosure of T and N and T is same as above phrase-structure grammar. isType2 ( ) function is checking whether grammar is of type 2 or not, a grammar is type 2 if all of its production α → β follow following rules α is single non-terminal i.e. α ∈ N β ∈ ( T + N ) * i.e. any combination of T and N and null isType1 ( ) function is checking whether grammar is of type 1 or not, a grammar is type 1 if all of its production α → β follow following rules α ∈ ( T + N ) * N ( T + N ) * , β ∈ ( T + N ) * N ( T + N ) * and | α | ≤ | β | i.e. LHS and RHS should contain at least one non-terminal and length of LHS should be less than RHS If α → ε then α should not be used in RHS in any productions where ε is represent null

8th Edition

ISBN: 9781260521337

Author: ROSEN

Publisher: MCG

See similar textbooks

Videos

Question

Chapter 13, Problem 1CP

To determine

To find the type of grammar for the given productions in a phase-structure grammar in the Chomsky classification scheme.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 13, Problem 30SE

Chapter 13, Problem 2CP

Students have asked these similar questions

120 High school students have to do 3 final exams to be able to enter to the university. There are exams in Math, CS and Language. We know: - 60 students passed Math - 40 students passed CS - 30 students passed CS and Math - 30 students passed Language and Math - 25 students passed CS and Language - 20 students passed Language and Math and CS - 50 students – failed all 3 exams. Draw a Venn Diagram to illustrate sets of students passing different exams. How many students passed Language?

The fill option in ggplot is part of the grammar of graphics. It is considered: Select one: a. Geometrics b. Aesthetics c. Themes d. facets e. Statistics

(3) Give a grammar G =(V.2,5, P), whereV =14, B,C;, =;a,b;,S =4, P: A- a4|bB, B- bC|aB,C aB|aC|2. (a) Is G a regular grammar? Why? (b) Find an nfa which accepts the language L(G). (c) Find the regular expression r associated with the language accepted by the above nfa. (d) Find regular language L(r) from the above r.

Chapter 13 Solutions

DISCRETE MATHEMATICS+ITS APPL. (LL)-W/A

Ch. 13.1 - Exercises 1-3 refer to the grammar with start...Ch. 13.1 - Exercises 1-3 refer to the grammar with start...Ch. 13.1 - Prob. 3E Ch. 13.1 - Let G=(V,T,S,P) be the phrase-structure grammar...Ch. 13.1 - Prob. 5E Ch. 13.1 - Prob. 6E Ch. 13.1 - Prob. 7E Ch. 13.1 - Show that the grammar given in Example 5 generates...Ch. 13.1 - Prob. 9E Ch. 13.1 - Prob. 10E

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

To find the type of grammar for the given productions in a phase-structure grammar in the Chomsky classification scheme.

Solution Summary: The author explains the Chomsky classification scheme's four types of grammar: Type 0 or unrestricted grammar, Type 2 or con-free grammar.

Videos

To find the type of grammar for the given productions in a phase-structure grammar in the Chomsky classification scheme.

Want to see the full answer?

Chapter 13 Solutions