Compilers Course - Homework

Page 1 of 1

3 Replies - 1212 Views - Last Post: 21 October 2016 - 10:53 AM

#1 orestis

Reputation: 0
• Posts: 3
• Joined: 20-October 16

Compilers Course - Homework

Posted 21 October 2016 - 08:19 AM

I was given an exercise set that ask me to write a regular expression (or deﬁnition) for each of the following languages, and I'm having a hard time doing because I'm not really experienced with this kind of regular expressions. Here are the answers I tried to give, can someone that is more experienced and has the knowledge to correct me if I'm wrong.

(a) Strings over the alphabet {a,b,c} where the ﬁrst a precedes the ﬁrst b

(B)/>/> Comments consisting of a string surrounded by /* and */

(c) All strings of 0’s and 1’s with an even number of 0’s , with at least two 0’s.

(d) {w ∈{a,b}*|w starts with a and contains bba as a substring }

Answer: ( a|b )* bba ( a|b )*

(e) {w ∈{0,1}*|w contains 111000 as a substring }

(f) {w ∈{0,1}*|w consists of alternating 0’s and 1’s }



Really not sure of any of my answers, if anyone can correct me if I'm wrong before I submit my answers I will be very grateful.

Is This A Good Question/Topic? 0

Replies To: Compilers Course - Homework

#2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12135
• Posts: 45,119
• Joined: 27-December 08

Re: Compilers Course - Homework

Posted 21 October 2016 - 08:25 AM

Moved to Computer Science.

Your answer for part (a) is not correct. It does not match c, ccc, cab, cacccab or \epsilon. Try and break down the cases better. You can have an a and b in the string, an a without b, neither an a nor b, no c's, etc.

I don't know what you're asking in (b).

For ©, you accept \epsilon, which has no 0's.

(e) Looks good.

(f) You accept 101101. Here, the middle 11 pair is not separated by a 0.

#3 orestis

Reputation: 0
• Posts: 3
• Joined: 20-October 16

Re: Compilers Course - Homework

Posted 21 October 2016 - 10:51 AM

Thanks a lot for your help, I have done most of them correct now I think. The next question asks me to explain why there is no regular expression deﬁning strings of a's and b's where there are more a's than b's. Why is that the case?

#4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12135
• Posts: 45,119
• Joined: 27-December 08

Re: Compilers Course - Homework

Posted 21 October 2016 - 10:53 AM

What do we know about regular languages? What tools do we have to show a language is not regular?