Question Paper: Automata Theory Question Paper - May 2017 - Information Technology (Semester 4) - Mumbai University (MU)
0

## Automata Theory - May 2017

### MU Information Technology (Semester 4)

Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary
1(a) Write regular expression to denote a language L which accepts all the strings which begin or end with either 00 or 11. 5 marks

1(b) Convert the given CFG to CNF
S→aSa|bSb|a|bS→aSa|bSb|a|b S\rightarrow aSa|bSb|a|b /
5 marks

1(c) Difference between FA and PDA 5 marks

1(d) Design moore machine to covert each occurrence of 111 to 101. 5 marks

2(a) Construct NFA with epsilon which accept a language consisting the string of any numbers of a's followed by any number of b's followed by any number of c's Also convert it into NFA witout epilson. 5 marks

2(b) Design a DFA corresponding to regular expression (a+b)* aba(a+b)* 5 marks

3(a) Use pumping lemma prove that whether following language is regular or not <mo stretchy="false">(</mo><msup><mi>a</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><msup><mi>b</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><msup><mi>c</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false">|</mo></mrow><mi>n</mi><mo>>=</mo><mn>1</mn><mo stretchy="false">)</mo>[/itex]" role="presentation" style="font-size: 125%; text-align: center; position: relative;">(anbncn|n>=1)<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><mo stretchy="false">(</mo><msup><mi>a</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><msup><mi>b</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><msup><mi>c</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false">|</mo></mrow><mi>n</mi><mo>>=</mo><mn>1</mn><mo stretchy="false">)</mo>[/itex]<script type="math/tex; mode=display" id="MathJax-Element-2">(a^{n}b^{n}c^{n}|n>=1)</script> 5 marks

3(b) Explain Chomsky's Hierarchy 5 marks

4(a) Definne context free grammar. Obtain the CFG for the following regular expression:
(110 + 11)* (10)*
5 marks

4(b) Convert given CFG to CNF
<merror><mtext>&S\rightarrow ASB|\varepsilon\&B\rightarrow SbS|A|bb\&A\rightarrow aAS|a</mtext></merror>[/itex]" role="presentation" style="font-size: 125%; text-align: center; position: relative;">&S\rightarrow ASB|\varepsilon\
&B\rightarrow SbS|A|bb\
&A\rightarrow aAS|a
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><merror><mtext>&S\rightarrow ASB|\varepsilon\&B\rightarrow SbS|A|bb\&A\rightarrow aAS|a</mtext></merror>[/itex]
<script type="math/tex; mode=display" id="MathJax-Element-3">&S\rightarrow ASB|\varepsilon\ &B\rightarrow SbS|A|bb\ &A\rightarrow aAS|a</script>
5 marks

5(a) Design a PDA to accept the language <mrow><mo>{</mo><mrow><mi>L</mi><mo>=</mo><msup><mi>a</mi><mrow class="MJX-TeXAtom-ORD"><mi>m</mi></mrow></msup><msup><mi>b</mi><mrow class="MJX-TeXAtom-ORD"><mi>m</mi></mrow></msup><msup><mi>c</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false">|</mo></mrow><mi>m</mi><mo>,</mo><mi>n</mi><mo>>=</mo><mn>1</mn></mrow><mo>}</mo></mrow>[/itex]" role="presentation" style="font-size: 125%; text-align: center; position: relative;">{L=ambmcn|m,n>=1}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><mrow><mo>{</mo><mrow><mi>L</mi><mo>=</mo><msup><mi>a</mi><mrow class="MJX-TeXAtom-ORD"><mi>m</mi></mrow></msup><msup><mi>b</mi><mrow class="MJX-TeXAtom-ORD"><mi>m</mi></mrow></msup><msup><mi>c</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false">|</mo></mrow><mi>m</mi><mo>,</mo><mi>n</mi><mo>>=</mo><mn>1</mn></mrow><mo>}</mo></mrow>[/itex]<script type="math/tex; mode=display" id="MathJax-Element-4">\left { L=a^{m}b^{m}c^{n}|m,n>=1 \right }</script> 5 marks

5(b) Construct TM for <mi>L</mi><mo>=</mo><mrow><mo>{</mo><mrow><msup><mi>a</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><msup><mi>b</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><msup><mi>c</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false">|</mo></mrow><mi>n</mi><mo>>=</mo><mn>1</mn></mrow><mo>}</mo></mrow>[/itex]" role="presentation" style="font-size: 125%; text-align: center; position: relative;">L={anbncn|n>=1}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><mi>L</mi><mo>=</mo><mrow><mo>{</mo><mrow><msup><mi>a</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><msup><mi>b</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><msup><mi>c</mi><mrow class="MJX-TeXAtom-ORD"><mi>n</mi></mrow></msup><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false">|</mo></mrow><mi>n</mi><mo>>=</mo><mn>1</mn></mrow><mo>}</mo></mrow>[/itex]<script type="math/tex; mode=display" id="MathJax-Element-5">L=\left { a^{n}b^{n}c^{n}|n>=1\right }</script> 5 marks

### Write short note any two question from Q.6(a, b, c)

6(a) Post Correspondence Problem 5 marks

6(b) Recursive and Recursively enumerable languages. 5 marks

6(c) Halting Problem 5 marks

question paper mu • 182 views