AUTOMATA Solution

For full source file email on vuhelps@gmail.com
Theory of Automata (CS402)
Assignment # 6
Total marks = 20
Deadline Date = 22-06-2009

Please carefully read the following instructions before attempting the assignment.

Rules for Marking
It should be clear that your assignment would not get any credit if:

 The assignment is submitted after due date.
 The submitted assignment does not open or file corrupt.
 The assignment is copied. Note that strict action would be taken if the submitted assignment is copied from any other student. Both students will be punished severely.

1) You should concern recommended books to clarify your concepts as handouts are not sufficient.
2) You are supposed to submit your assignment in MS Word format and any other formats like scan images, PDF, Zip, rar, docx format etc will not be accepted
3) You are advised to upload your assignment at least two days before Due date.


Important Note: Assignment comprises of 3 questions. Note that no assignment will be accepted after due date via email in any case (whether it is the case of load shedding or emergency electric failure or internet malfunctioning etc.). Hence, refrain from uploading assignment in the last hour of the deadline, and try to upload assignments at least 02 (two) days before the assignment to avoid inconvenience later on.

Q1) consider the CFG given below: [marks 5]

S  aSa | bSb | a | b | aa | bb

Convert the above CFG in Chomsky Normal Form (CNF).


Answer:
To convert the above CFG to be in CNF, introduce the new productions as
A a, B b, then the new CFG will be
S ASA|BSB|AA|BB|a|b
A a
B b
Introduce nonterminals R1 and R2 so that
S AR1|BR2|AA|BB|a|b
R1 SA
R2 SB
A a
B b
which is in CNF.
It may be observed that the above CFG which is in CNF generates the NONNULLPALINDROME, which does
not contain the null string.



















Q2) consider the Regular Expression given below: [Marks 10]

RE = (a+b)*a

Draw the FA of the above RE according to New Format, given in Lecture 37.

Answer:
FA accepts the language of strings, expressed by (a+b)*a.

Q3) Briefly explain “PUSHDOWN STACK” in your own words. [Marks 5]
Answer:
A PUSHDOWN STACK is a place where input letters can be strode until we want to refer to them again. It holds the letters it has been fed in a long column/ The operation PUSH adds a new letter to the top of the column. The new letter is placed on top of the STACK, wand all the other letters are pushed back accordingly before the machine begins to process an input string the STACK is presumed to be empty which means that every storage location init initially contains a blank. If the STACK is then fed the letters a, b, c, d by the sequence of instructions
PUSH a
PUSH b
PUSH c
PUSH d
Then the top letter in the STACK is D the second is c the third is b and the fourth is a, if we now execute the instruction