Scribd
Upload
69 views1 page

ISE ATCD Assignment-2

The document contains 10 questions about automata theory and compiler design for an assignment. The questions cover topics like constructing strings from grammars using derivatives, designing context free grammars, determining if grammars are ambiguous, finding derivations trees, proving languages are/aren't regular, minimizing automata, converting automata to regular expressions, drawing DFAs to recognize languages, and implementing transition diagrams in C.

Uploaded by

cutie
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
69 views1 page

ISE ATCD Assignment-2

The document contains 10 questions about automata theory and compiler design for an assignment. The questions cover topics like constructing strings from grammars using derivatives, designing context free grammars, determining if grammars are ambiguous, finding derivations trees, proving languages are/aren't regular, minimizing automata, converting automata to regular expressions, drawing DFAs to recognize languages, and implementing transition diagrams in C.

Uploaded by

cutie
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

DEPARTMENT OF INFORMATION SCIENCE AND ENGINEERING

ASSIGNMENT - 1
Subject title: Automata Theory and Compiler Design
SUB CODE: 21CS51 SEM: V Marks:10 Last Date of Submission:16-02-2024

Q1 Derive leftmost and rightmost derivatives to construct the strings (i) CO 3,


aabbba, (ii) baabab, (iii) aaabbb for the following grammar. CO 4
S→AS|ε ; A→aa|ab|ba|bb BL 4
Q2 Design CFG for the following grammar. CO 3,
L={ai bj ck|i=j+k} CO 4
BL 4
Q3 For the following grammar, S→A1B; A→0A | ε; B→0B|1B| ε CO 3,
(i) Show that this grammar is unambiguous. CO 4
(ii) Find a grammar for the same language that that is ambiguous BL 2
and demonstrate its ambiguity.
Q4 The following grammar generates prefix expression with operands x and CO 3,
y and binary operators +, -,and *; E→+EE | *EE | -EE |x |y CO 4
(i) Find leftmost and rightmost derivations tree for the string **- BL 3
xyxy.
(ii) Prove that this grammar is unambiguous.
Q5 Prove that the following languages are not regular languages. CO 3,
(i) L={0n 1n | n>=1}; (ii) L={0n 1m 2n | n and m are arbitrary CO 4
integers}: (iii) L={0n 1m | n<=m}; (iv) L={0n 12n | n>=1} BL 3
Q6 Prove that the following languages are not regular languages. CO 3,
(i) The set of strings of 0,s and 1,s that are of the form ww that is CO 4
some string is repeated. BL 3
(ii) The set of strings of 0’s and 1’s that are of the form wwR that
is some string followed by its reverse
(iii) L={ap | p is a prime}.
Q7 Minimize the following automata.
CO 3,
CO 4
BL 3

Q8 Convert the following automata into regular expression


CO 3,
CO 4
BL 3

Q9 CO 3,
Draw DFA to recognise the language token using CD definitions ,
CO 4
(i) a(a | b)*a ; (ii) ((ε|a)b*)* ; (iii) a*ba*ba*ba*
BL 2
Q10 Implement the following using c-program. CO 4,
(i) Transition diagram of id. (ii) Transition diagram of keyword. (iii) CO 5
Transition diagram of white space. BL 4

You might also like