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

#1 orestis  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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 definition) 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 first a precedes the first b 

Answer: ab*(c*|ε)

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

Answer: /* (a*|b*|c*)* */

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

Answer: (1*01*01*)*

(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 } 

Answer: (0|1)* 111000 (0|1)*

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

Answer: (010 | 101)* 


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  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12187
  • View blog
  • Posts: 45,250
  • 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.

For (d), you accept bba, which does not start with a.

(e) Looks good.

(f) You accept 101101. Here, the middle 11 pair is not separated by a 0.
Was This Post Helpful? 1
  • +
  • -

#3 orestis  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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 defining strings of a's and b's where there are more a's than b's. Why is that the case?
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12187
  • View blog
  • Posts: 45,250
  • 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?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1