-1
$\begingroup$

Let the Grammar be G = ({S}, Σ, P, S), where Σ = {⟨,⟩,[,]} and

P: S → ⟨S⟩, [S], SS, ε 
[⟨ → ⟨[

Can I still use the CYK-Algorithm and if yes then how would I do it for a word like ⟨[]⟩ ?

$\endgroup$
5
  • $\begingroup$ I don't understand your notation in the quoted block. I don't understand what either line is trying to say. Can you use more standard notation for grammars? ote that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – D.W.
    Jan 16 at 20:58
  • $\begingroup$ What are your thoughts? What are the guarantees on what kinds of grammars CYK is guaranteed to work for? If you read some resources on CYK, you should be able to answer that. Then, is this grammar one of those kinds of grammars? You have used the context-free tag. Is this a context-free grammar? What are your thoughts on that? Please edit your question to show your progress and your thoughts. (continued) $\endgroup$
    – D.W.
    Jan 16 at 20:59
  • $\begingroup$ We're not particularly looking for questions that are the statement of an exercise-like task and a request for us to solve it for you, as those are unlikely to be helpful to you in the long run or helpful to others after you. $\endgroup$
    – D.W.
    Jan 16 at 20:59
  • 1
    $\begingroup$ Your grammar doesn't appear to be context-free. CYK only works for context-free grammars. $\endgroup$ Jan 16 at 22:25
  • 1
    $\begingroup$ Please don't append "Edit: more stuff". See cs.meta.stackexchange.com/q/657/755. If you discover the answer to your own question, please don't edit the question to put it in the question. Instead, write an answer using the 'Your Answer' box below. $\endgroup$
    – D.W.
    Jan 17 at 15:52

1 Answer 1

1
$\begingroup$

the Grammar is not context-free and thus the CYK -Algorithm wont work

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.