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

DISCRETE MATHEMATICS LOOSELEAF W/CONNECT

8th Edition

ISBN: 9781264309405

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

Given that the outward flux of a vector field through the sphere of radius r centered at the origin is 5(1 cos(2r)) sin(r), and D is the value of the divergence of the vector field at the origin, the value of sin (2D) is -0.998 0.616 0.963 0.486 0.835 -0.070 -0.668 -0.129

10 The hypotenuse of a right triangle has one end at the origin and one end on the curve y = Express the area of the triangle as a function of x. A(x) =

Are there any unusually high or low pH levels in this sample of wells?

Chapter 13 Solutions

DISCRETE MATHEMATICS LOOSELEAF W/CONNECT

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