@shopan: can you write a regular expression that recognizes the same language? If so it is. If not it either isn't or you didn't try hard enough :) but usually the thing that makes things non regular have to do with "counting" things, like the language of matched parens.
Just try to write an equivalent re and see if it works or not
you _could_ also prove something formally if you know formal language theory but I don't expect you to do that :)
The 5th line of the context-free grammer reads
ReplyDelete"VP -> V NP % simple VP"
I assume "V" should be "Verb". Yes?
Does the lexicon implicitly includes entries like:
ReplyDeleteDet -> "" (empty string)
otherwise "flies" can't be parsed under this grammar.
@Chris: Yes, "V" should be "Verb" -- thanks for catching that.
ReplyDelete@Tony: Shoot, there should have been a rule "NP -> Noun".
I've added these two the homework file; so please download the new one!
Fig 5.18 in J&M gives the state space for a particular observed sequence. Should we just ignore the observed variables for part 1.1? (Can we, please?)
ReplyDeleteFor question 1.1, do we make up one possible observation (e.g. "C, S, D") and draw the state space lattice for it?
ReplyDeletehow can we determine if a grammar is regular or not ?
ReplyDelete@shopan: can you write a regular expression that recognizes the same language? If so it is. If not it either isn't or you didn't try hard enough :) but usually the thing that makes things non regular have to do with "counting" things, like the language of matched parens.
ReplyDeleteJust try to write an equivalent re and see if it works or not
you _could_ also prove something formally if you know formal language theory but I don't expect you to do that :)