Scribd
Upload
120 views4 pages

Tutorial 1 Discussion Document - Batch 03

1) The document provides examples of context-free grammars and the languages they generate. It also asks questions about defining languages using set notation and constructing grammars for regular expressions. 2) For questions about context-free grammars, the response uses set notation to precisely define the language generated by each grammar through derivations. 3) For regular expressions, grammars are constructed with nonterminals that generate the corresponding regular languages. Valid and invalid strings are used to illustrate the languages.

Uploaded by

Anindya Costa
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
120 views4 pages

Tutorial 1 Discussion Document - Batch 03

1) The document provides examples of context-free grammars and the languages they generate. It also asks questions about defining languages using set notation and constructing grammars for regular expressions. 2) For questions about context-free grammars, the response uses set notation to precisely define the language generated by each grammar through derivations. 3) For regular expressions, grammars are constructed with nonterminals that generate the corresponding regular languages. Valid and invalid strings are used to illustrate the languages.

Uploaded by

Anindya Costa
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 1 discussion – Batch 03

Worked Example

1) Use set notation to define the language of the grammar below:


S → aS | aA | c
A → Ab | λ
L = {w ϵ {aic| i ≥ 0} U {ai bj | i ≥ 1; j ≥ 0}}
S => c
S => aS => ac
S => aS => aaS => aac

S => aA => a
S => aS => aaA => aa
S => aS => aaS => aaaA => aaa

S => aA => aAb => ab


S => aA => aAb => aAbb => abb
S => aA => aAb => aAbb => aAbbb => abbb

S => aA => aAb => ab


S => aS => aaA => aaAb => aab
S => aS => aaS => aaaA => aaaAb => aaab

S => aA => aAb => ab


S => aS => aaA => aaAb => aaAbb => aabb

2) Construct a grammar over {a, b} that recognizes the language {aib2i | i ≥ 1}

Example valid strings: abb, aabbbb, aaabbbbbb, etc.

Invalid Strings: a, ab, aba…

S → abb | aSbb

S => abb

S => aSbb => aabbbb

S => aSbb => aaSbbbb => aaabbbbbb


Questions:

1) For each of the following grammars, use set notation to define the language generated by the
grammar.
a) S → aaSB | λ
B → bB | b

L = {w ϵ {a^2i b^i | i ≥ 1}}

L = {w ϵ {a^2i b^j | i ≥ 0, j ≥ 0}}

L = {w ϵ {a^2i b^j | i ≥ 1, j ≥ 1 }} U λ

S => λ
S => aaSB => aaB => aab
S => aaSB => aaaaSBB => aaaaBB => aaaabB => aaaabb
S => aaSB => aaB => aab
S => aaSB => aaB => aabB => aabb

2
b) L = {w ϵ {a, b}* | w has odd length} //* can take a value 0 to ∞ In grammar, Upper case
letters are called as non-
Example valid strings: a, b, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaaa, ababa etc.. terminals. Meaning, they can
be expanded.
S → a | b | SSS
Lower case letters are called
S => a as terminals. Meaning, they
S => b cannot be expanded. Always,
S => SSS => aSS => aaS => aaa alphabets will be terminals.
S => SSS => SSSSS
Left most derivation or right most derivation.

S → a | aA | b | bA
A → aS |bS
S => a
S => aA => aaS => aaa
S => aA => aaS => aaaA => aaaaS => aaaaa
S => b
S => bA => bbS => bbb
S = aA => abS => aba

c) {w ϵ {a, b}* | w has b’s followed by a’s}

e.g., strings are: ba, bbaa, baa, bbbbaaaaaaaaaaaaaaa


e.g., invalid strings: ab, bab, baba
The above grammar is right and it is one possible answer.

e) L = {w ϵ {a, b} |w is {anbn | n ≥ 0}}


e.g., e, ab, aabb, aaabbb and so on…
abab

S → λ | ab | aSb
S => aSb => aaSbb => aaabbb
S => aSb => ab
S => ab

S → λ | aSb

S => aSb => ab


S => aSb => aaSbb => aabb

3. For each of the following Regular Expressions, write a regular grammar that defines the same
language.

b) L = (a υ b υ c)* a(a υ b υ c)* b(a υ b υ c)* υ (a υ b υ c)* b(a υ b υ c)* a(a υ b υ c)*

a b U ba

(a υ b υ c)*
w = e, a, b, c, aa, ab, ac, bb, cc, bc, cb, ca, ba, aaa, abc, cba, bac, cab, bbb, etc.

A = (a υ b υ c)*

S → AaAbA | AbAaA
A → e | aA | bA | cA

A => aA => a
A => aA => aaA => aa
A => bA => baA => bacA => bac
c) a(a υ b υ c)* b(a υ b υ c)*

S → aAbA
A → λ | aA | bA | cA

You might also like