Scribd
Upload
69 views4 pages

Tutorial 1 Discussion Document - Batch 01

The document provides examples of using set notation to define languages generated by context-free grammars. It also gives regular expressions and asks to write equivalent regular grammars. Key questions covered include defining languages over {a,b} involving prefixes like aib2i, strings with odd length, and strings matching patterns like having b's followed by a's. Regular expressions covered include a*b*c* and expressions combining a, b, c. Corresponding regular grammars are provided.

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
69 views4 pages

Tutorial 1 Discussion Document - Batch 01

The document provides examples of using set notation to define languages generated by context-free grammars. It also gives regular expressions and asks to write equivalent regular grammars. Key questions covered include defining languages over {a,b} involving prefixes like aib2i, strings with odd length, and strings matching patterns like having b's followed by a's. Regular expressions covered include a*b*c* and expressions combining a, b, c. Corresponding regular grammars are provided.

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 document – Batch 01:

Worked Example:

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

Answer:
S → aS | aA | c
A → Ab | λ L = {w ϵ {aic | i ≥ 0} U {aibj | i ≥ 1; j ≥ 0}}

S => c
S => aS => ac
S => aS => aaS => aac
S => aS => aaS => aaaS => aaac

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

S => aA => a
S => aA => aAb => ab
S => aA => aAb => aAbb => abb

S => aA => aAb => ab


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

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

e.g., valid strings: abb, aabbbb, aaabbbbbb

in valid strings: baa, aba, a, b, aaaaaaaaaaaaaaaaa, bbabababab etc

S → abb |aSbb

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 ∈ { {a2i bj} | i ≥ 1, j ≥ i} ∪ {λ}}

The above language is correct.

2)
b) L = {w ϵ {a, b}* | w has odd length}
e.g., a, b, aaa, bbb, aab, aba, abb, baa, bab, bba, aaaaa, etc.. (Infinite number of odd length strings)

S → a | b |SSS

S => SSS => aSS => aaS => aaa

S => SSS => bSS => bbS => bbb

S => SSS => aSS => aaS => aab

S => SSS => SSSSS

S → a | b| aA |bA

A → aS |bS

S => aA => aaS => aab

S => aA => aaS => aaaA => aaaaS => aaaaa

S => bA => bbS => bbb

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


Example valid strings are: ba, baa, bbba

baba is an invalid string.

S → bA | bS

A → a | aA

The above grammar is one possible solution.

S => bS => bbA => bbaA => bbaaA => bbaaa

S => bA

e) L = {w ϵ {an bn | n ≥ 0} }

f) L = {w ϵ {anbn cm| n ≥ 0, m ≥ 1}}

g) L = {w ϵ {ambn cm| m ≥ 0, n ≥ 1}}

Regular Expressions:

e.g., L = (ab U ba)*

e.g., strings: e, ab, ba, abab, abba, baba, baab, ababab, baabbab, etc.
3. For each of the following Regular Expressions, write a regular grammar that defines the same
language.
a) a*b*c*

e.g., valid strings are: e, a, b, c, ab, ac, bc, abc, aabc, abbbbc, abbcccc, aaaaaa, bbb, ccccc,
etc.

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

A a A b A U A b Aa A

A = (a υ b υ c)*

e.g., valid strings are: e, a, b, c, aa, bb, cc, ab, ac, ba, bc, ca, aaa, bbb, ccc, abc, cba, cab, bac,

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

A => cA => caA => cabA => cab


A => aA => abA => abcA => abc
A => aA =>a
A => aA => aaA => aa

A => bA => b

A => bA => bbA => bb

c) a(a υ b υ c)* b(a υ b υ c)*

S -> aAbA
A -> e | aA | bA | cA

You might also like