Formal Languages and Automata

Page 1 of 1

6 Replies - 1748 Views - Last Post: 26 June 2012 - 02:11 PM

#1 insbroker   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 26-June 12

Formal Languages and Automata

Posted 26 June 2012 - 09:55 AM

The following two questions concern the following grammar:
S -> bAB
A -> bB | a
B -> aA | λ

6.1. Which of the following is a correct derivation for bbaaab?

a. S => bAB => bAaA => bbAaA => bbaaA => bbaaaB => bbaaab

b. S => bAB => bbBB => bbBaA => bbBabB => bbaAabB => bbaaabB => bbaaab

c. S => bAB => bbBB => bbBaA => bbBabB => bbaaabB => bbaaab

d. S => bAB => bbBB => bbBaB => bbAabA => bbaAabB => bbaaabB => bbaaab

I chose b, is that right?

Is This A Good Question/Topic? 0
  • +

Replies To: Formal Languages and Automata

#2 sepp2k   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2770
  • View blog
  • Posts: 4,429
  • Joined: 21-June 11

Re: Formal Languages and Automata

Posted 26 June 2012 - 10:02 AM

Yes, that's right. All the other derivations either contain an invalid step or are doing two steps in one.
Was This Post Helpful? 0
  • +
  • -

#3 denting5   User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 84
  • Joined: 03-June 12

Re: Formal Languages and Automata

Posted 26 June 2012 - 01:52 PM

I know that I am a novice poking around in the forums that I do not understand, but could you please drop a link to an explanatory text?
Was This Post Helpful? 0
  • +
  • -

#4 modi123_1   User is offline

  • Suitor #2
  • member icon



Reputation: 16479
  • View blog
  • Posts: 65,313
  • Joined: 12-June 08

Re: Formal Languages and Automata

Posted 26 June 2012 - 01:57 PM

Quote

explanatory text

Of what part?
Was This Post Helpful? 0
  • +
  • -

#5 denting5   User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 84
  • Joined: 03-June 12

Re: Formal Languages and Automata

Posted 26 June 2012 - 02:00 PM

View Postmodi123_1, on 26 June 2012 - 01:57 PM, said:

Quote

explanatory text

Of what part?

I'm sorry to admit, just about the whole thing.
Was This Post Helpful? 0
  • +
  • -

#6 modi123_1   User is offline

  • Suitor #2
  • member icon



Reputation: 16479
  • View blog
  • Posts: 65,313
  • Joined: 12-June 08

Re: Formal Languages and Automata

Posted 26 June 2012 - 02:09 PM

*Sigh*.. so you've hit the formal language wiki link, right?


edit:

Generative grammar
https://www.msu.edu/...omp-lecture.pdf
Was This Post Helpful? 0
  • +
  • -

#7 denting5   User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 84
  • Joined: 03-June 12

Re: Formal Languages and Automata

Posted 26 June 2012 - 02:11 PM

Err...um...nervous giggle...um...eh...er... sort of-kinda-ish?
Was This Post Helpful? 0
  • +
  • -
Page 1 of 1