I am taking a course on natural language processing that assumes the students have some background on theory of computation. I dont, but have read up till chapter 3 of the book "Speech and Language Processing by Jufrasky".

I therefore understand the following

  • regular expressions and regular languages
  • operations on regular languages (union, cross product)
  • finite state automatas and the construction of FSA's given a regular expression

Unfortunately, I couldn't solve a single question below and am not even sure if my understanding of the question is correct. The red ticks are the solutions. I hope the people here can help out an NLP newbie.

Definitions for the notations are as follows:

$+$ which means ‘one or more of the previous character’. (book definition)

$\bigotimes$ cross product

So this is my most likely wrong understanding of the first statement: $L_1+ \bigotimes L_2 + $

If I have

$L_1 = \{aa,ab,aab\}$

$L_2 = \{b,ab,abb\}$

then $L_1 + $ requires me to have at least one occurrence of $L_1$. And so $L_1+ \bigotimes L_2 + $ would result in a set that could have at least one of the element from $L_1$ concatenated with at least one from $L_2$ ? So I could get something like $aa \ aa \ b$ ? Where the two $aa$ comes from $L_1$.

Would this be correct ?

enter image description here

  • 1
    $\begingroup$ Sorry, there's a lot of back-and-forth here and I'm losing track. Could you please just add a clear definition of $\otimes$ and $\circ$ to your question. Jufrasky is using nonstandard notation and nonstandard terminology. $\endgroup$ – David Richerby Mar 11 '18 at 15:38
  • 1
    $\begingroup$ Is it possible that these exercises are about rational relations and finite state transducers instead of regular languages? In this case $L_1 \otimes L_2 = \{(aa, b), (ab, b), (aab, b), (aa, ab), (ab, ab), (aab, ab), (aa, abb), (ab, abb), (aab, abb)\}$ with $L_1, L_2$ from the languages in the question. Consequently, the composition would be defined like $(u, u') \circ (v, v') = (uv, u'v')$. $\endgroup$ – ttnick Mar 11 '18 at 17:24
  • 1
    $\begingroup$ I'm confused. I can't tell what your question is. Can you pick a single conceptual question you are not sure about and ask about that? Are you asking us to explain what the notation means? Are you asking us to check whether your solution is correct? Are you asking us to solve one of these exercises? Can you narrow the question down to focus on just one thing? If you can't solve the exercise, that usually means there is some concept you don't understand. Can you identify what that concept is, and ask just about the concept? $\endgroup$ – D.W. Mar 11 '18 at 17:42
  • 1
    $\begingroup$ Cross-posted: cs.stackexchange.com/q/89191/755, math.stackexchange.com/q/2685601/14578, cstheory.stackexchange.com/q/40354/5038. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Mar 11 '18 at 17:44
  • 1
    $\begingroup$ If you don't even know how to start, often that means there's some concept you don't understand or aren't quite clear on. If you can figure out what that is, asking about that concept tends to lead to a better question -- one that is more focused, and that is more likely to be useful to others in the future. $\endgroup$ – D.W. Mar 11 '18 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.