Во время упражнения я должен написать не зависящую от контекста грамматику для следующего языка:
Я не уверен, что полностью понимаю подход, но вот что я получил.
Так как нам нужно по крайней мере 1 c в окружении любых равных чисел a и b х (может быть ноль) Я придумал следующий CFG:
T --> aCb | aTb | C
C --> cS | cC
S --> empty
Сверху я могу, например, никогда не создавать строки, по крайней мере, 1 c в этом. Но я могу создать строку только с c и без a или b . Аналогично я могу создавать строки с aa ... c ... bb (с любым числом a 's и b с 1 c между), а также любые строки, аналогичные предыдущим, но с любым числом c как хорошо.
Тем не менее, я чувствую, что этот CTF несколько сложнее, чем нужно. Может кто-нибудь сказать мне, как улучшить, если, или в случае, если это неправильно - что мне не хватает?
Редактировать: после некоторых хороших входных данных от rici что я прибыть сейчас:
T --> aTb | cC
C --> cC | empty
Удаляя любую избыточность (такую как aCb, которая может быть достигнута с помощью aTb и C), а также нетерминальную S.