Пусть Σ = { a; b} Как я могу определить КПК в JFLAP, который распознает следующее?

Question

L = {a^n b^k | 2n >= k}

Например: abb является элементом L, aabbb является элементом L, ε является элементом L, но babbb не является элементом L, abbb не является элементом L

Answer 1

Самая короткая строка в L пустая строка, e, Учитывая строку s на языке действуют следующие правила:

1. as в L
2. asb в L
3. asbb в L

Мы можем объединить эти наблюдения, чтобы получить грамматику без контекста:

S := aSbb | aSb | aS | e

По нашим наблюдениям, каждая строка, генерируемая этой грамматикой, должна быть в L, Чтобы показать, что это грамматика для Lмы должны показать, что любая строка в L может быть сгенерировано. Чтобы получить строку a^n b^k мы можем сделать следующее:

1. используйте правило № 1 выше x раз
2. используйте правило № 2 выше y раз
3. используйте правило № 3 выше z раз
4. обеспечивать x + y + z = n
5. обеспечивать y + 2z = k

настройка y = k - 2z и подставляя мы находим x + k - 2z + z = n, Перегруппировка:

1. если k > n, затем z а также x может быть выбран, однако желательно, пока k - n = z - x,
2. если k < n, затем z а также x может быть выбран, однако желательно, пока n - k = x - z,
3. Если k = nЗаметьте, мы могли бы просто выбрать y = n,

Обратите внимание, что мы всегда можем выбрать z а также x в нашем примере выше, так как 0 <= x, z <= n а также 0 <= k <= 2n,