www.vustudents.ning.com

We non-commercial site working hard since 2009 to facilitate learning Read More. We can't keep up without your support. Donate.

# CS402 Theory of Automata Assignment#05 Solution & Discussion Due Date: 07-07-2011

### Assignment No.5

Your assignment must be uploaded before or on 7th July, 2011 [Try to upload your solution well before due date to avoid any issue]

### Rules for Marking

It should be clear that your assignment will not get any credit if:

• The assignment is submitted after due date
• The assignment is copied

### Objectives

Objective of this assignment is to make students able to understand the following concepts,

• CNF
• PDA

### CNF

Convert the CFG (Context Free Grammar) given below to CNF (Chomsky Normal Form)

### PDA

Design Push Down Automata (PDA) for

(ba)n(ab)n                  n = 1,2,3…

Hint:

You can push single a on reading ‘ba’ (in loop) and once you get ‘a’ again after reading ‘ba’ start popping pushed a’s against each occurrence of ‘ab’ . You will move to accept state if you have empty stack (∆ on pop) on finish of input string (reading ∆)

Upload single word file in word 2003 format having solutions for all questions.

Views: 296

### Replies to This Discussion

Attachments:
yes please some one help us we are already busy to study the final term exam metrial
yes you are right
Lagta hey mjhe he solution upload krna pre ga..............
Question No.1 CNF
Convert the CFG (Context Free Grammar) given below to CNF (Chomsky Normal Form)
Solution
To convert the above CFG to be in CNF, introduce the new productions as
X --> xxy, Y --> Xw then the new CFG will be.

S --> XYX
X --> XXY
Y --> XW

Introduce non- terminals so that,

S -->XR1
R1 -->YX
X --> XR2
R2 --> XY
Y --> XW
X --> xxy
Y --> Xw
See the attached file for one more idea solution of CS402 Assignment#05 Spring 2011
Attachments:

1

2

3

4

5

## Latest Activity

33 minutes ago
1 hour ago
иαвєєℓ αнмє∂ posted discussions
1 hour ago

### Poetry

2 hours ago
♥ + Kamli + ♥ liked иαвєєℓ αнмє∂'s discussion !!!! Yaad !!!!
2 hours ago
♥ + Kamli + ♥ liked иαвєєℓ αнмє∂'s discussion !!!! Chalo Mana !!!!!
2 hours ago
♥ + Kamli + ♥ liked иαвєєℓ αнмє∂'s discussion !!! Kahin sy tu aajaaa !!!
2 hours ago
♥ + Kamli + ♥ liked ASIM!!'s discussion Faisla
2 hours ago