[PDF] CS 311 Homework 5 Solutions Oct 28 2010 L = {0n1m0n





Previous PDF Next PDF



CS3350 Pumping Lemma Let us prove that L = {anbncn n ? 0} is

Let us prove that L = {anbncn n ? 0} is not a regular language. For this



Practice Problems for Final Exam: Solutions CS 341: Foundations of

Answer: There exist constants c and n0 such that





Homework 6 Solutions

Note that A is a regular language so the language has a DFA. Use the pumping lemma to prove that the language A = { 02n 13n 0n



CS 341 Homework 9 Languages That Are and Are Not Regular

(j) If L1 and L2 are nonregular languages then L1 ? L2 is also not regular. 4. Show that the language L = {anbm : n ? m} is not regular. 5. Prove or 



proving languages not regular using Pumping Lemma

If L is a regular language then there is an integer n > 0 with the property that: (*) for any string x ? L where



? n

v



CS 311 Homework 5 Solutions

Oct 28 2010 L = {0n1m0n



m

we will use a proof by contradiction. Assume.



Theory of Computation - (Finite Automata)

Jan 24 2021 What about strings with size n where n mod k = i? ... Problem. Prove that L = {anbn



Homework 4

Suppose that language A is recognized by an NFA N and language B is the collection of strings not accepted by some DFA M. Prove that A ? B is a regular 



CS 311 Homework 5 Solutions

due 16:40, Thursday, 28 thOctober 2010

Homework must be submitted on paper, in class.

Question 1.[30 pts.; 15 pts. each]

Prove that the following languages are not regular using the pumping lemma. a.L=f0n1m0njm;n0g.

Answer.

To prove thatLis not a regular language, we will use a proof by contradiction. Assume thatLis regular. Then by the Pumping Lemma for Regular Languages, there exists a pumping length,pforLsuch that for any strings2Lwherejsj p,s=xyzsubject to the following conditions: (a)jyj>0 (b)jxyj p, and (c)8i >0;xyiz2L. Chooses= 0p10p. Clearly,jsj pands2L. By condition (b) above, it follows that xandyare composed only of zeros. By condition (a), it follows thaty= 0kfor some k >0. Per (c), we can takei= 0 and the resulting string will still be inL. Thus, xy

0zshould be inL.xy0z=xz= 0(pk)10p. But, this is clearly not inL. This is a

contradiction with the pumping lemma. Therefore our assumption thatLis regular is incorrect, andLis not a regular language. b.L=fwtwjw;t2 f0;1g+g.

Answer.

To prove thatLis not a regular language, we will use a proof by contradiction. Assume thatLis a regular language. Then by the Pumping Lemma for Regular Languages, there exists a pumping lengthpforLsuch that for any srings2Lwherejsj p, s=xyzsubject to the following conditions: (a)jyj>0 (b)jxyj p, and (c)8i >0;xyiz2L. 1 Chooses= 0p110p1. Clearlys2Lwithw= 0p1 andt= 1, andjsj p. By condition (b), it is obvious thatxyis composed only of zeros, and further, by (a) and (b), it follows thaty= 0kfor somek >0. By condition (c), we can take anyiandxyizwill be inL. Takingi= 2, thenxy2z2L.xy2z=xyyz= 0(p+k)110p1. There is no way that this string can be divided intowtwas required to be inL, thusxy2z =2L. This is a contradiction with condition (c) of the pumping lemma. Therefore the assumption thatLis a regular language is incorrect and thusLis not a regular language.

Question 2.[20 pts]

Convert the following DFA into a regular expression using state elimination. Be sure to show intermediate steps of the process.q1q2q0 b aa b a bAnswer. First we introduce a new start and nal state, with"transitions to and from the original start and nal states.2 Now we remove state q2, and reconnect state q1 to q0, including the regular expression for

the path through q2 along with the original path from q1 to q0.Now remove q1, adding the regular expression for the path through q1 to the self-loop on

q0.Finally, remove state q0, connecting the start and nal state with the regular expression for

the self-loop on q0. This regular expression represents all the strings that this NFA accepts.Question 3.[20 pts.; 10 pts. each]

Write context free grammars that generate the following languages. In each case use the alphabet =f0;1g. a.fx#yj jxj 6=jyjg: 3

Answer.

To construct this grammar, we will build a balanced string of arbitrary length, and then force the generation to choose between a path that forces either the left or the right side to be arbitrarily longer than the other side.

S!XSXjXLjRX

L!#jXL

R!#jRX

X!0j1 b.fwjwcontains at least two occurences of the substring 101g This language is straightforward. Force the inclusion of two occurences of the substring

101 right in the rst rule. Then allow arbitrary other substrings to be placed in all

other positions.

S!A101A101A

A!AAj0j1j"

Question 4.[30 pts; 15 pts. each]

Construct PDAs that recognize the following languages: a.L=faibjji > jg

Answer.

This machine will count the number ofas by pushing them on the stack. Then it will start comparingbs from the input withas on the stack. When all thebs are consumed, then the machine will drain the stack and accept if there are stillas on the stack. So long as there areas on the stack, then the string ofbs must be shorter. 4 b.L=fxcyjx;y2 fa;bgand^x6=yRg This machine will push everything onto the stack until it reads thec. Then it will attempt to match the stack against the input, consuming input so long as it matches. The machine will accept if it sees one set of mis-matched characters, or if either part is longer than the other. In all other cases, the machine will get stuck without accepting.5quotesdbs_dbs19.pdfusesText_25
[PDF] prove boolean expression truth table

[PDF] prove that a^2^n is not regular

[PDF] prove that the following languages over a b c are not regular

[PDF] provincial court of appeal canada

[PDF] proxy maroc telecom

[PDF] ps eden space java

[PDF] pso clustering python code

[PDF] psychology paper outline example

[PDF] psychometric numerical reasoning test+pdf

[PDF] psychometric test pdf with answers

[PDF] psychometric test preparation books

[PDF] psychometric test questions and answers

[PDF] pt terms anatomy

[PDF] ptak.eu

[PDF] ptaszarnia eu