.cyk() method of CFG class appears to be incorrect sometimes.

[BigTuna08]

I'm not sure exactly what the problem is, here is an example, it is saying the null string is not accepted but it should be

Variables (V): {'B', 'A', 'S'}
Terminals (Σ): {'λ', '1', '0'}
Null character: λ
Start variable (S): S
Rules (R):
S -> 0S1B | ABA
A -> 1S00 | λ
B -> λ
11111 in grammer: False
1111 in grammer: False
1010101 in grammer: False
1100 in grammer: False
1010 in grammer: False
0 in grammer: False
1101 in grammer: False
0011 in grammer: True
λ in grammer: False
in grammer: False

Here is the code to replicate

from cfg import CFG

variables= {"A", "B", "S"}
terminals= {"0", "1", 'λ'}
null_char = 'λ'

symbols = variables.union(terminals)
symbols

test_strings = ["11111", "1111", "1010101", "1100", "1010", "0", "1101", "0011", 'λ', ""]

rules = [('S', 'ABA'), ('S', '0S1B'), ('A', 'λ'), ('A', '1S00'), ('B', 'λ')]

grammer = CFG(variables= variables,
terminals= terminals,
rules = set(rules),
start_variable = "S",
null_character = 'λ'
)

print(grammer)
for s in test_strings:
print(f"{s} in grammer: {grammer.cyk(s)}",)

[mahdavipanah]

This project is for a couple of years ago and unfortunately, I cannot remember the exact details but you are more than welcome to create a merge request for it.

…

On Thu, Oct 7, 2021 at 02:03 BigTuna08 ***@***.***> wrote: I'm not sure exactly what the problem is, here is an example, it is saying the null string is not accepted but it should be Variables (V): {'B', 'A', 'S'} Terminals (Σ): {'λ', '1', '0'} Null character: λ Start variable (S): S Rules (R): S -> 0S1B | ABA A -> 1S00 | λ B -> λ 11111 in grammer: False 1111 in grammer: False 1010101 in grammer: False 1100 in grammer: False 1010 in grammer: False 0 in grammer: False 1101 in grammer: False 0011 in grammer: True λ in grammer: False in grammer: False Here is the code to replicate from cfg import CFG variables= {"A", "B", "S"} terminals= {"0", "1", 'λ'} null_char = 'λ' symbols = variables.union(terminals) symbols test_strings = ["11111", "1111", "1010101", "1100", "1010", "0", "1101", "0011", 'λ', ""] rules = [('S', 'ABA'), ('S', '0S1B'), ('A', 'λ'), ('A', '1S00'), ('B', 'λ')] grammer = CFG(variables= variables, terminals= terminals, rules = set(rules), start_variable = "S", null_character = 'λ' ) print(grammer) for s in test_strings: print(f"{s} in grammer: {grammer.cyk(s)}",) — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAKVIVQQQZFHT2GBCMG3UYDUFTISVANCNFSM5FP6CMGQ> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.