[go: up one dir, main page]
Scribd
Upload
36 views4 pages

Focs Tutorial2

The document discusses context free grammars and pumping lemmas. It contains 7 questions about writing context free grammars for various languages, drawing PDAs for languages, proving languages are inherently ambiguous or not context free using the pumping lemma, and showing a language is not context free.

Uploaded by

tjcomprocker
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
36 views4 pages

Focs Tutorial2

The document discusses context free grammars and pumping lemmas. It contains 7 questions about writing context free grammars for various languages, drawing PDAs for languages, proving languages are inherently ambiguous or not context free using the pumping lemma, and showing a language is not context free.

Uploaded by

tjcomprocker
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
You are on page 1/ 4

Tutorial 2

Foundations of Computing Science

INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR

Pallab Dasgupta
Professor,
Dept. of Computer Sc & Engg

Questions
1. Write Context Free Grammar for the following languages :
a) {w|w contains at least three 1s} , ={0,1}
b) {w|w starts and ends with the same symbol}
c) {w| the length of w is odd}
d) {w| the length of w is odd and its middle symbol is a 0}
e) The set of strings over the alphabet {a,b} with more as than bs
f) L= {anb2nck | n, k 1}
g) {w#x | wR is a substring of x for w, x {0,1}*}

INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR

2. Draw the PDA for the following languages:


a) L1 = { amwcwrbm | w {0, 1} + and m 1}
b) L2 = {anbm | m n}
c) The set of palindromes over {a, b}

3. For the language :


A={aibjck | i=j or j=k where i,j,k>=0}
a) Give a context-free grammar that generates A
b) Show that the language A is inherently ambiguous

4. Let CFG G be the following grammar.


S -> aSb | bY| Ya
Y -> bY|aY|

Give a simple description of L(G) in English. Use that description to give a CFG for the
complement of L(G)
5. Convert the following CFG into an equivalent CFG in Chomsky Normal Form
A->BAB | B |

INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR

B-> 00 |

6. Using the pumping lemma for CFL, show that the following languages ( A, B, C and D ) are not
context-free:

a) A = { 0n1n0n1n | n 0 }
b) B = { 0n#02n#03n | n 0 }
c) C = { w#t | w is a substring of t, where w,t {a,b}* }

d) D = { wtwR | w,t {0,1}* and |w| = |t| }


7. Prove the following:

INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR

(a) Let C be a context-free language and R be a regular Language. Prove that the language C
R is context-free
(b) Let A={w|w {a,b,c}* and w contains equal number of as, bs and cs}. Use (a) to show that
A is not a CFL.

You might also like