wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

Context-Free Grammar

Total questions: 98

Worksheet time: 49mins

Name
Class
Date
1.

What is a rule in a Context-Free Grammar (CFG)?

a)

A rule can be applied only in a specific context

b)

A rule can be applied anywhere the single non-terminal (variable) on the left side appears, regardless of its context (surrounding symbols)

c)

A rule can be applied only if there are multiple variables on the left side

d)

A rule can be applied only to terminal symbols

2.

Rule Format: Fill in the blank for the rule format in a Context-Free Grammar (CFG): ____ → β (Only a single variable on the left side)

a)

A → β

b)

A B → β

c)

a → β

d)

A → aB

3.

The language L = {aⁿbⁿ | n ≥ 1} requires an equal number of a's and b's. Which of the following strings belong to this language? Select all that apply.

a)

ab

b)

aabb

c)

aaabbb

d)

aabbb

e)

abbb

4.

Which of the following best describes the language L = anbn∣n≥1a^n b^n | n ≥ 1 ?

a)

The language requires an equal number of a's and b's (e.g., ab, aabb, aaabbb).

b)

The language requires more a's than b's.

c)

The language requires more b's than a's.

d)

The language requires only a's.

5.

Fill in the blank: The CFG rules for the language L are: S → aSb S → __

a)

ab

b)

ba

c)

aabb

d)

bbaa

6.

Fill in the blank: The parsing example for deriving 'aabb' is: S → aSb → a(ab)b → __

a)

aabb

b)

abab

c)

aaab

d)

abb

7.

Why does the rule S → aSb work for generating strings in the language L = {a^n b^n | n ≥ 1}?

a)

It always expands to aSb, generating a's and b's simultaneously and enforcing count equality.

b)

It generates only a's.

c)

It generates only b's.

d)

It does not enforce count equality.

8.

What is Chomsky Normal Form (CNF)?

a)

A way to represent Regular Grammars

b)

A highly restricted and standardized way to represent Context-Free Grammars (CFGs)

c)

A method for parsing ambiguous grammars

d)

A type of finite automaton

9.

Chomsky Normal Form (CNF) enforces that every single production rule in the grammar must strictly follow one of two simple structures.

a)

True

b)

False

10.

Which type of production in formal grammar requires a non-terminal (A) to derive exactly two non-terminals (B and C)?

a)

Binary Production

b)

Terminal Production

c)

Phrase Production

d)

Word Production

11.

Fill in the blank: In Terminal Production, a non-terminal (A) must derive exactly ___ terminal symbol (a, a real word/character).

a)

one

b)

two

c)

three

d)

zero

12.

What is the primary role of CNF?

a)

To make rules more complex

b)

To enable efficient and algorithmic parsing (understanding sentence structure) by a computer

c)

To slow down parsing algorithms

d)

To remove binary branching

13.

Fill in the blank: The rules in Complex CFG are ______ and complex, while the rules in CNF are simple and uniform.

a)

arbitrary

b)

fixed

c)

predictable

d)

uniform

14.

Which algorithm requires CNF to work and is used for efficient parsing?

a)

CYK Algorithm (Cocke-Younger-Kasami)

b)

Dijkstra's Algorithm

c)

Merge Sort

d)

Binary Search

15.

CNF forces the Parse Tree to be Binary Branching (two branches always).

a)

True

b)

False

16.

What is the original complex rule (Non-CNF) shown in the example?

a)

S → open AB close

b)

S → AB open close

c)

S → open close AB

d)

S → AB close open

17.

According to the example, what is the difficulty in the original complex rule?

a)

Mixing terminals with non-terminals and having more than two symbols on the right side.

b)

Mixing only terminals.

c)

Having only one symbol on the right side.

d)

Mixing non-terminals only.

18.

Fill in the blank: The CNF solution breaks the single complex rule down into ______ simple binary steps and two terminal steps.

a)

three

b)

four

c)

five

d)

two

19.

Fill in the blank: S → ________

a)

X_open Z_1

b)

Y_closed Z_2

c)

X_closed Z_3

d)

Y_open Z_4

20.

Fill in the blank: Z_1 → ________

a)

A Z_2

b)

B Z_3

c)

C Z_4

d)

D Z_5

21.

Fill in the blank: Z_2 → ________

a)

B X_close

b)

A Y_open

c)

C Z_far

d)

D W_near

22.

Fill in the blank: X_open → ________

a)

open

b)

close

c)

start

d)

exit

23.

Fill in the blank: X_close → ________

a)

close

b)

open

c)

exit

d)

start

24.

What is the result of the simplification process described?

a)

The computer only has to check for simple binary pairs (X and Z_1) at every step, making the analysis structured and fast.

b)

The computer must evaluate all possible combinations at each step, increasing complexity.

c)

The process eliminates the need for binary analysis entirely.

d)

The result is a random selection of binary pairs at each step.

25.

Which of the following is NOT a valid rule in Chomsky normal form?

a)

A) A → BC

b)

B) A → a

c)

C) A → B

d)

D) S → ε (where S is the start variable)

26.

In Chomsky normal form, 'a' is any _________.

a)

terminal

b)

non-terminal

c)

production

d)

variable

27.

In Chomsky normal form, the rule S → ε is permitted if S is the start variable.

a)

True

b)

False

28.

In Chomsky normal form, what do B and C represent in the rule A → BC?

a)

B and C are any variables or terminals other than the start variable.

b)

B and C are always terminal symbols.

c)

B and C are always the start variable.

d)

B and C are always epsilon (empty string).

29.

Fill in the blank: The first step to convert any CFG to Chomsky normal form is to _________.

a)

Add a new start symbol

b)

Remove useless symbols

c)

Eliminate left recursion

d)

Convert to Greibach normal form

30.

Fill in the blank: The second step to convert any CFG to Chomsky normal form is to eliminate ε rules of the form _________

a)

A → ε

b)

A → a

c)

A → B

d)

A → AB

31.

Fill in the blank: The third step to convert any CFG to Chomsky normal form is to eliminate unit rules of the form _________

a)

A → B

b)

A → a

c)

A → ε

d)

A → BC

32.

Fill in the blank: The fourth step to convert any CFG to Chomsky normal form is to convert remaining rules into proper form, which means _________?

a)

2 non-terminal or 1 terminal

b)

1 non-terminal or 2 terminals

c)

3 non-terminals or 1 terminal

d)

2 terminals or 1 non-terminal

33.

According to the instructions for converting a CFG to Chomsky normal form, what is the new rule that should be created after adding a new start symbol?

a)

S₀ → S

b)

S → S₀

c)

S₀ → ε

d)

S → ε

34.

In the process of converting a CFG to Chomsky normal form, which symbol is the start symbol?

a)

S₀

b)

S

c)

CFG

d)

Chomsky

35.

What is the second step in converting a CFG to Chomsky normal form?

a)

Eliminate all ε rules A → ε, where A is not the start variable

b)

Add new rules with A deleted

c)

Replace R → A with R → ε

d)

Remove all terminal symbols

36.

Fill in the blank: For each rule with an occurrence of A on the right-hand side, add a new rule with the ____ deleted.

a)

A

b)

left-hand side

c)

terminal

d)

start symbol

37.

If we have R → A, what should we replace it with unless we had already removed R → ε?

a)

R → ε

b)

R → A

c)

R → uAv

d)

R → uv

38.

Given the rule R → uAv, what does it become after eliminating ε rules?

a)

R → uAv | uv

b)

R → uAvAw | uvAw | uAvw | uvw

c)

R → ε

d)

R → A

39.

Given the rule R → uAvAw, what does it become after eliminating ε rules?

a)

R → uAvAw | uvAw | uAvw | uvw

b)

R → uAv | uv

c)

R → ε

d)

R → A

40.

What is the form of unit rules that need to be eliminated?

a)

A → B

b)

A → a

c)

A → BC

d)

A → ε

41.

When converting a CFG to Chomsky normal form, what should you do for each rule B → u when eliminating unit rules?

a)

Replace B → u with all rules of the form u → w in the grammar.

b)

Remove B → u from the grammar without replacement.

c)

Change B → u to B → ε.

d)

Add a new non-terminal for each rule B → u.

42.

Convert a CFG to Chomsky normal form: What is the process repeated until all unit rules have been replaced?

a)

Repeat until all unit rules have been replaced.

b)

Remove all terminal symbols from the rules.

c)

Eliminate all left recursion in the grammar.

d)

Add new start symbols to every production.

43.

What is left to do in this step?

a)

Complete the remaining task in this step.

b)

Start a new project.

c)

Review the previous step.

d)

Skip to the final step.

44.

Convert a CFG to Chomsky normal form Step 4: Convert remaining rules into proper form (2 variables or one terminal) Fill in the blanks for the rule transformation:

a)

A → u₁A₁, A₁ → u₂A₂, ..., Aₖ₋₂ → uₖ₋₁uₖ

b)

A → u₁u₂u₃, A₁ → u₄u₅, ..., Aₖ₋₂ → uₖuₖ₊₁

c)

A → u₁A₁A₂, A₁ → u₂A₂A₃, ..., Aₖ₋₂ → uₖ₋₁Aₖ

d)

A → u₁, A₁ → u₂, ..., Aₖ₋₂ → uₖ

45.

What is the production rule for S in the given grammar?

a)

S → S₁ | S₂

b)

S → S₂ | S₁

c)

S → S₁b | Ab

d)

S → aAb | ab | ε

46.

Fill in the blank: The production rule for S₁ is S₁ → _____

a)

S₁b | Ab

b)

S₁a | Aa

c)

S₁c | Ac

d)

S₁d | Ad

47.

Which of the following is NOT a production for A?

a)

aAb

b)

ab

c)

ε

d)

S₁b

48.

Fill in the blank: The production rule for S₂ is S₂ → _____

a)

S₂ → S₂a | Ba

b)

S₂ → aS₂ | aB

c)

S₂ → aB | S₂a

d)

S₂ → Ba | aS₂

49.

What is the production rule for B in the given grammar?

a)

B → bBa | ba | ε

b)

B → S₂a | Ba

c)

B → aAb | ab | ε

d)

B → S₁b | Ab

50.

Step 1: Add a new start symbol. Why is adding a new start symbol important in grammar transformation?

a)

It helps to avoid ambiguity and ensures the original start symbol is preserved.

b)

It makes the grammar more complex without any benefit.

c)

It removes all non-terminals from the grammar.

d)

It guarantees that the grammar becomes left-recursive.

51.

Fill in the blank in the production rule: S₁ → S₁b | ___b

a)

Ab

b)

Bb

c)

Sb

d)

aB

52.

Fill in the blank in the production rule: A → aAb | ab | ___

a)

ε

b)

a

c)

b

d)

A

53.

Fill in the blank in the production rule: S₂ → S₂a | ___a

a)

Ba

b)

Sa

c)

Aa

d)

Ca

54.

Fill in the blank: S₀ → ___

a)

S

b)

A

c)

B

d)

C

55.

Fill in the blank: S → ___ | ___

a)

S₁ | S₂

b)

S | S

c)

A | B

d)

S₁ | B

56.

Fill in the blank: S₁ → S₁b | Ab | ___

a)

b

b)

a

c)

S₁a

d)

Abc

57.

Fill in the blank: A → aAb | ___

a)

ab

b)

aA

c)

bA

d)

aBb

58.

Fill in the blank: S₂ → S₂a | Ba | ___

a)

a

b)

B

c)

S₂

d)

S

59.

Fill in the blank: B → bBa | ___

a)

ba

b)

Bb

c)

aB

d)

bB

60.

What is the purpose of Step 3 in the example?

a)

Add new unit rules

b)

Eliminate all unit rules

c)

Add new non-terminals

d)

Eliminate all productions

61.

Step 4: Convert remaining rules to proper form. Fill in the blank: S₀ → ________

a)

S₁b | Ab | b | S₂a | Ba | a

b)

S₁a | Ab | a | S₂b | Ba | b

c)

S₁b | Ab | a | S₂a | Ba | b

d)

S₁a | Ab | b | S₂b | Ba | a

62.

Step 4: Convert remaining rules to proper form. Fill in the blank: S → ________

a)

S₁b | Ab | b | S₂a | Ba | a

b)

S₁a | Aa | a | S₂b | Bb | b

c)

S₁b | Aa | b | S₂a | Bb | a

d)

S₁a | Ab | a | S₂b | Ba | b

63.

Step 4: Convert remaining rules to proper form. Fill in the blank: S₁ → ________

a)

S₁b | Ab | b

b)

S₁a | Aa | a

c)

S₁c | Ac | c

d)

S₁d | Ad | d

64.

Step 4: Convert remaining rules to proper form. Fill in the blank: A → ________

a)

aAb | ab

b)

aA | b

c)

abA | a

d)

Aab | b

65.

Step 4: Convert remaining rules to proper form. Fill in the blank: S₂ → ________

a)

S₂a | Ba | a

b)

S₂a | Bb | b

c)

S₂b | Ba | a

d)

S₂a | Ba | b

66.

Step 4: Convert remaining rules to proper form. Fill in the blank: B → ________

a)

bBa | ba

b)

Ba | bA

c)

bA | Ba

d)

bB | ab

67.

Fill in the blank: S₀ → ________

a)

S₁b | Ab | b | S₂a | Ba | a

b)

S₁a | Bb | a | S₂b | Ab | b

c)

S₂b | Ba | b | S₁a | Ab | a

d)

Ab | S₁b | S₂a | Ba | b | a

68.

Fill in the blank: S → ________

a)

S₁b | Ab | b | S₂a | Ba | a

b)

S₁a | Ab | a | S₂b | Ba | b

c)

S₁c | Ac | c | S₂d | Bd | d

d)

S₁d | Ad | d | S₂c | Bc | c

69.

Fill in the blank: S₁ → ________

a)

S₁b | Ab | b

b)

S₁a | Aa | a

c)

S₁c | Ac | c

d)

S₁d | Ad | d

70.

Fill in the blank: A → ________

a)

aAb | ab

b)

aB | ab

c)

aAb | a

d)

aA | ab

71.

Fill in the blank: S₂ → ________

a)

S₂a

b)

S₂b

c)

S₂c

d)

S₂d

72.

Fill in the blank: B → ________

a)

bBa | ba

b)

Ba | bA

c)

bA | Ba

d)

bB | a

73.

Fill in the blank: A1 → ________

a)

a

b)

b

c)

c

d)

d

74.

Fill in the blank: B1 → ________

a)

b

b)

a

c)

c

d)

d

75.

What is the production rule for S₀ in the original grammar?

a)

S₁B1 | AB1 | b | S₂A1 | BA1 | a

b)

S₁b | Ab | b | S₂a | Ba | a

c)

S₁B1 | AB1 | b

d)

S₂A1 | BA1 | a

76.

Fill in the blank: The production rule for A1 is ______.

a)

a

b)

b

c)

c

d)

d

77.

After adding terminals, what is the main problem mentioned in the image regarding the variables?

a)

Variables become undefined.

b)

Variables are duplicated.

c)

Variables are not initialized.

d)

Variables are incorrectly named.

78.

What is the production rule for B in the transformed grammar?

a)

B1BA1 | B1A1

b)

bBa | ba

c)

B1BA1 | B1A1 | bBa | ba

d)

ba

79.

Fill in the blank: The production rule for B1 is ______.

a)

b

b)

a

c)

c

d)

d

80.

Which rule in the original grammar produces the terminal 'a'?

a)

A1 → a

b)

A2 → b

c)

A3 → c

d)

A4 → d

81.

Fill in the blank: S₀ → ______

a)

S₁A1 | AB1 | b | S₂A1 | BA1 | a

b)

S₁A2 | AB2 | c | S₂A2 | BA2 | d

c)

S₁B1 | AA1 | e | S₂B1 | BB1 | f

d)

S₁C1 | AC1 | g | S₂C1 | BC1 | h

82.

Fill in the blank: S₁ → ______

a)

S₁B1 | AB1 | b

b)

S₁A1 | BB1 | a

c)

S₁C1 | AC1 | c

d)

S₁D1 | AD1 | d

83.

Fill in the blank: A → ______

a)

A1AB1 | A1B1

b)

A1A | B1A1

c)

A1B1 | AB1A1

d)

A1B1A | 1A1B

84.

Fill in the blank: S₂ → ______

a)

S₂A1 | BA1 | a

b)

S₂A2 | BA2 | b

c)

S₂A3 | BA3 | c

d)

S₂A4 | BA4 | d

85.

Fill in the blank: B → ______

a)

B1BA1 | B1A1

b)

B2BA2 | B2A2

c)

B1AB1 | B1A2

d)

B2AB2 | B2A1

86.

Fill in the blank: A1 → ______

a)

a

b)

b

c)

c

d)

d

87.

Fill in the blank: B1 → ______

a)

b

b)

a

c)

c

d)

d

88.

Fill in the blank: A2 → ______

a)

A1A

b)

A3B

c)

B2A

d)

C2A

89.

Fill in the blank: B2 → ______

a)

B1B

b)

B3B

c)

B2A

d)

B4C

90.

Fill in the blank: S0 → S1A1 | AB1 | b | S2A1 | BA1 | ____

a)

a

b)

bA1

c)

A2

d)

S1B

91.

Fill in the blank: S1 → S1B1 | AB1 | ____

a)

b

b)

aB1

c)

S1A

d)

B1

92.

Fill in the blank: A → A2B1 | ____

a)

A1B1

b)

A2B2

c)

B1A2

d)

B2A1

93.

Fill in the blank: S2 → S2A1 | BA1 | ____

a)

a

b)

b

c)

c

d)

d

94.

Fill in the blank: B → B2A1 | ____

a)

B1A1

b)

B2B1

c)

A2B1

d)

B1B2

95.

Fill in the blank: A1 → ____

a)

a

b)

b

c)

c

d)

d

96.

Fill in the blank: B1 → ____

a)

b

b)

a

c)

c

d)

d

97.

Fill in the blank: A2 → ____

a)

A1A

b)

A3B

c)

B2A

d)

C2A

98.

Fill in the blank: B2 → ____

a)

B1B

b)

B2B

c)

B3B

d)

BB2

Similar Resources on Wayground

qatar set 2

100 questions

qatar set 2

quiz

Worksheet

•

Professional Development

Test your brain

103 questions

Test your brain

quiz

Worksheet

•

1st Grade - Professio...

mathematic 100

100 questions

mathematic 100

quiz

Worksheet

•

KG - Professional Dev...

Latihan MTK KLS 9

100 questions

Latihan MTK KLS 9

quiz

Worksheet

•

Professional Development

examen

100 questions

examen

quiz

Worksheet

•

Professional Development

Midterm Exam for Educ1

100 questions

Midterm Exam for Educ1

quiz

Worksheet

•

Professional Development

Vocabulary and Grammar Quiz

93 questions

Vocabulary and Grammar Quiz

quiz

Worksheet

•

Professional Development

Sept-June

100 questions

Sept-June

quiz

Worksheet

•

Professional Development