Scribd
Upload
7 views2 pages

Formal Language Grammar Tutorial

The document presents a series of exercises related to formal grammars, including identifying grammar types, demonstrating language membership for specific strings, and drawing derivation trees. It covers various grammars with different sets of non-terminal and terminal symbols, production rules, and asks for analysis of generated strings and languages. The exercises focus on understanding the properties and behaviors of context-free and phrase-structure grammars.

Uploaded by

2025161973
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views2 pages

Formal Language Grammar Tutorial

The document presents a series of exercises related to formal grammars, including identifying grammar types, demonstrating language membership for specific strings, and drawing derivation trees. It covers various grammars with different sets of non-terminal and terminal symbols, production rules, and asks for analysis of generated strings and languages. The exercises focus on understanding the properties and behaviors of context-free and phrase-structure grammars.

Uploaded by

2025161973
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Tutorial 8 (Formal Language)

[Link] the following grammar G:


V = {S, A, B}
T = {a, b}
P = {S →AB, A →Aa, A →a, B→Bb, B→b}
S is the start symbol.

i. What is the type of the above grammar?


ii. Show that the word a2b3 belongs to this language.

2. Consider the grammar G = {V, T, S, P}, which is describe by its non-


terminal symbols V = { B, C }, terminal symbols T = { a, b, c }, starting
symbol S and production P={ S → a S B C | a B C, cB → BC, a B → a b, bB →bb, bC
→ bc, c C → cc }.

i. State the type of grammar G with reason(s).


ii. Draw the conversion for aabbcc.

3. Let G be the Grammar with V = {a,b,c,S}; T = {a,b,c}; starting symbol S; and productions
S → abS, S → bcS, S →a, and S → cb. Determine whether the following string is accepted by
the Grammar or NOT.
i. bcbba
ii. bccbbb
iii. bbbcbba
iv. bcabbbbbcb
v. abbbcba

4. Let G = (V, T, S, P) be the phrase-structure grammar with V = {0, 1, A, S}, T = {0, 1},
and set of productions P consisting of S → 1S, S → 00A, A → 0A, and A → 0.

i) Show that 111000 belongs to the language generated by G.


ii) Show that 11001 does not belong to the language generated by G.
iii) What is the language generated by G?

5. Consider the grammar G = ( {S}, {a,b}, S, P) with the production are;


S → aSa
S → bSb
S → Ɛ

i. What is the type of grammar (G)?


ii. Compute some strings generated by the above production rules of grammar G.
6. Consider the grammar G = (V, T, S, P), which is described by its non-terminal symbols
V={S, X, Y}, terminal symbols T = {1, 0}, starting symbol S and production
P = {S → XY, X → 1X, X → 0, Y → 1}.

i. State the type of grammar G with reason(s).

ii. Draw the derivation tree for 11101.

7. Consider the following grammar G:


V = {S, A, B, C, 1, 0}
T = {1, 0}

P = {S →1AB, A →1A |1, B →00B | }

S is the start symbol.

i. Give 2 strings generated by the grammar.


ii. Describe the language define by the grammar G above.

You might also like