Обычный язык (да или нет)

Мне дали задание проверить, является ли этот язык регулярным:

L = {w∈{a,b,c}* | where the number of a is less than the number of b+c.}

Я не могу найти для этого ни регулярного выражения, ни детерминированного (или нет) конечного автомата. С другой стороны, я не нашел способа доказать обратное с помощью теоремы о накачке.

Любые идеи?


regex regular-language automata
person Giannis Vl    schedule 10.12.2011    source источник
comment
Я думаю, что это не так, но я не получил достаточно CS, чтобы сказать наверняка, почему. Что-то, связанное с законностью a, в зависимости не от того, что следует за ним или предшествует ему, а от того, достаточно ли b или c во всей строке. Это не всегда. Я не уверен, что это вообще без контекста.   -  person cHao    schedule 10.12.2011
comment
Я считаю, что E в приведенном выше уравнении следует заменить на ∈.   -  person Jan    schedule 10.12.2011
comment
Это похоже на то, что я делал в гугле. :) О, и похоже, что язык, по крайней мере, контекстно-независимый, хотя я не могу сделать его регулярным.   -  person cHao    schedule 10.12.2011

Ответы (1)


arrow_upward
3
arrow_downward

Отказ от ответственности

Я знаю, что формальное доказательство с использованием леммы о накачке было опубликовано выше. Тем не менее, я выберу полностью неформальное объяснение, потому что я считаю, что это обычно помогает иметь некоторую интуицию в отношении проблемы, прежде чем искать формальное решение.

Общая интуиция

В общем, когда язык зависит от какого-то типа счета, это должно сигнализировать о том, что он, вероятно, не является правильным. Причина в том, что счетчик может быть сколь угодно большим. Вы можете увидеть это конкретно на своем примере.

Почему не регулярно?

Представьте, что вы пытаетесь создать DFS для вашего языка. Что вас волнует, так это разница между количеством a и суммой количества b и c (назовите это D_abc). В DFS вся информация фиксируется в самом состоянии. В качестве примера рассмотрим состояние после чтения 10 последовательных a и состояние после чтения 100 последовательных a. Эти два состояния должны быть разными. Теперь, расширяя этот аргумент для любого количества a (или, что эквивалентно, любого D_abc), вы можете сделать вывод, что вам нужно бесконечное количество состояний, т.е. язык не является регулярным.

Бонус: почему он контекстно-свободный?

А теперь подумайте об использовании автомата с выталкиванием вниз. КПК позволяет фиксировать сложность (бесконечного) счета, используя свой (бесконечный) стек. В вашем примере вы можете сделать это так:

  • Если стек пуст (т. Е. D_abc = 0), вставьте в стек любой встреченный символ (т. Е. Если появляется a, D_abc <- 1, иначе, если появляется b или c D_abc <- -1).

  • Если верхним элементом стека является a (т. Е. D_abc> 0), если появляется a, вставьте его в стек (т. Е. D_abc <- D_abc + 1, иначе вытолкните верх a из стека (т. Е. D_abc <- D_abc - 1).

  • Точно так же, если верхним элементом является b или c (т.е. D_abc < 0), если появляется b или c, вставьте его в стек (т.е. D_abc <- D_abc - 1), иначе удалите верхний элемент из стека (т.е. D_abc <- D_abc + 1).

Используя приведенные выше правила, стек в каждый момент времени ведет счетчик D_abc, а это именно то, что вам нужно, чтобы принять или не принять строку. Таким образом, можно сделать вывод, что язык контекстно-свободный.

person 3lectrologos    schedule 10.12.2011