Дан язык SuperParanthesis , состоящий из терминалов "(", ")" и "<>" (как один символ).

Скобочки выполняют привычную для всех группировку. "<>" закрывает все открытые скобочки.

Примеры слов в языке:
((()))
(()(()()<>
(<>()()()(((())<><><>

Это не в языке:
(((<>)

Вопрос: Возможно ли написать context-free (контекстно-независимую?) грамматику для языка SuperParanthesis?
Желательно, отвечать аргументированно .

ЗЫ. Вопрос теоретический, никаких вариантов "нет, но можно обойти" и т.п. не надо.

Свой вариант пока не привожу, т.к. не уверен, что он правильный, а сбивать вас с мысли не хочется.

С уважением,
fAX.

Здравствуйте, fAX, Вы писали:

fAX>Дан язык SuperParanthesis , состоящий из терминалов "(", ")" и "<>" (как один символ).

fAX>Скобочки выполняют привычную для всех группировку. "<>" закрывает все открытые скобочки.

<expr> ::= ( ( '(' | <expr> )* '<>' | '(' <expr> ')' )*

В BNF переписывать влом...

Здравствуйте, m.a.g., Вы писали:

MAG>Здравствуйте, fAX, Вы писали:

fAX>>Дан язык SuperParanthesis , состоящий из терминалов "(", ")" и "<>" (как один символ).

fAX>>Скобочки выполняют привычную для всех группировку. "<>" закрывает все открытые скобочки.

MAG>

MAG><expr> ::= ( ( '(' | <expr> )* '<>' | '(' <expr> ')' )*
MAG>

А вот и нет:

( ( ) ( <> ) — не в языке.

Здравствуйте, fAX, Вы писали:

MAG>>

MAG>><expr> ::= ( ( '(' | <expr> )* '<>' | '(' <expr> ')' )*
MAG>>

fAX>А вот и нет:

fAX>( ( ) ( <> ) — не в языке.



<expr> ::= ( ( '(' | <prim> )* '<>' | <prim> )*
<prim> ::= '(' <prim>* ')'

Здравствуйте, fAX, Вы писали:

fAX>Скобочки выполняют привычную для всех группировку. "<>" закрывает все открытые скобочки.

fAX>Вопрос: Возможно ли написать context-free (контекстно-независимую?) грамматику для языка SuperParanthesis?

Попробуем...

Продукционная грамматика:

String  --> ^ ClosedN $

ClosedN -->
ClosedN --> Closed ClosedN

Closed  --> <>                 пустой блок
Closed  --> ( ExactN )         правильный блок
Closed  --> ( OpenN <>         блок с аварийным завершением

ExactN  -->
ExactN  --> Exact ExactN

Exact   --> ( ExactN )

OpenN   -->
OpenN   --> Open OpenN

Open    --> ExactN
Open    --> ( Open

значком ^ обозначается начало строки, $ - конец

Правила редукции

( )   -->
( <>  --> <>
^ <>  --> ^
^ $   --> $

Стековый автомат

вершина | результат
стека   | на стеке
+ вход  |
--------+-----------
^ (     | ^ (
( )     |
( <>    | <>
^ <>    | ^
^ $     |

Автомат на счетчике:

n>=0

n (   --> n+1
n )   --> n-1
n <>  --> 0
0 $   --> 0

Здравствуйте, fAX, Вы писали:

fAX>Здравствуйте, m.a.g., Вы писали:

MAG>>Здравствуйте, fAX, Вы писали:

fAX>>>Дан язык SuperParanthesis , состоящий из терминалов "(", ")" и "<>" (как один символ).

fAX>>>Скобочки выполняют привычную для всех группировку. "<>" закрывает все открытые скобочки.

fAX>А вот и нет:

fAX>( ( ) ( <> ) — не в языке.

Возможно, я плохо объяснил:
"<>" — выполняет закрытие всех скобочек, и любая ")" сразу после него заранее нелегальна! Можно смотреть на этот терминал как на контекстно-зависимый терминал, расширяемый в нужное количество закрывающих скобочек.

( ( )<> ()      - OK
(()()(<>)       - Illegal
((((((<>()<>(<> - OK.

Вопрос, можно ли написать контекстно-независимую грамматику?

Здравствуйте, Кодт, Вы писали:

К>Автомат на счетчике:
К>

n>>=0

К>n (   --> n+1
К>n )   --> n-1
К>n <>  --> 0
К>0 $   --> 0
К>

С этим согласен, но это уже более мощный автомат, нежели стэковый — стэковый оперирует только с конечными числами.


Остальное — смотрю.

Здравствуйте, fAX, Вы писали:

fAX>Вопрос, можно ли написать контекстно-независимую грамматику?

Так моя поправленная грамматика правильна?

Здравствуйте, Кодт, Вы писали:


К>Попробуем...

К>Продукционная грамматика:
К>

К>String  --> ^ ClosedN $

К>ClosedN -->
К>ClosedN --> Closed ClosedN

К>Closed  --> <>                 пустой блок
К>Closed  --> ( ExactN )         правильный блок
К>Closed  --> ( OpenN <>         блок с аварийным завершением

К>ExactN  -->
К>ExactN  --> Exact ExactN

К>Exact   --> ( ExactN )

К>OpenN   -->
К>OpenN   --> Open OpenN

К>Open    --> ExactN
К>Open    --> ( Open

К>значком ^ обозначается начало строки, $ - конец
К>

Пока ничего возразить не могу. Долго писали?

Здравствуйте, m.a.g., Вы писали:

MAG>Здравствуйте, fAX, Вы писали:

fAX>>Вопрос, можно ли написать контекстно-независимую грамматику?

MAG>Так моя поправленная грамматика правильна?
Нет, скобочки лишние в конце вылазят

MAG>>Так моя поправленная грамматика правильна?
fAX>Нет, скобочки лишние в конце вылазят

Где???

Здравствуйте, fAX, Вы писали:
fAX>С этим согласен, но это уже более мощный автомат, нежели стэковый — стэковый оперирует только с конечными числами.

Неправда! Стековый автомат не слабее арифметического.
Пусть язык L включает в себя t терминальных и n нетерминальных символов, итого
p = ||L|| = t+n.
Тогда снимок стека (длиной s) можно представить s-значным числом по основанию p.

---

Примем, что 1-ричные числа — это числа N = "1......1" (N цифр: N = 1^(N-1) + ... 1*1^0).
Поэтому значение счетчика эквивалентно стеку ("стопке фишек") данной высоты/глубины.
Дно стека эквивалентно 0.

---

Счетчиковый автомат в общем случае слабее стекового, поскольку он реализует стек из единичек.

Здравствуйте, fAX, Вы писали:

fAX>Пока ничего возразить не могу. Долго писали?

Быстро придумал, написал за 15 минут (с отвлечениями), еще минут 5 — на верификацию.

Больше всего тормозов ушло на то, чтобы избежать не-L-рекурсии

x --> x y

-----

x --> y x
y --> a x b

и в медитации над "контекстной независимостью" (хотя она тут очевидна, зачем я голову ломал).

Здравствуйте, fAX, Вы писали:

fAX>Свой вариант пока не привожу, т.к. не уверен, что он правильный, а сбивать вас с мысли не хочется.

Судя по твоему посту, нельзя.
Но надо подумать.

Здравствуйте, vasketsov, Вы писали:

V>Судя по твоему посту, нельзя.
V>Но надо подумать.

А судя по моему посту?

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, fAX, Вы писали:
fAX>>С этим согласен, но это уже более мощный автомат, нежели стэковый — стэковый оперирует только с конечными числами.

К>Неправда! Стековый автомат не слабее арифметического.
К>Пусть язык L включает в себя t терминальных и n нетерминальных символов, итого
К>p = ||L|| = t+n.
К>Тогда снимок стека (длиной s) можно представить s-значным числом по основанию p.

К>

---

К>Примем, что 1-ричные числа — это числа N = "1......1" (N цифр: N = 1^(N-1) + ... 1*1^0).
К>Поэтому значение счетчика эквивалентно стеку ("стопке фишек") данной высоты/глубины.
К>Дно стека эквивалентно 0.

К>

---

К>Счетчиковый автомат в общем случае слабее стекового, поскольку он реализует стек из единичек.
Я думал Вы имеете в виду добавить отнять произвольные числа (например, n = n + n).

Здравствуйте, m.a.g., Вы писали:


MAG>>>Так моя поправленная грамматика правильна?
fAX>>Нет, скобочки лишние в конце вылазят

MAG>Где???

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

... Что я могу сказать... Был неправ...

Здравствуйте, fAX, Вы писали:

К>>Счетчиковый автомат в общем случае слабее стекового, поскольку он реализует стек из единичек.
fAX>Я думал Вы имеете в виду добавить отнять произвольные числа (например, n = n + n).

Это не имеет значение. Добавить произвольное число K — это положить K фишек сверху.
Убавить — это снять.
Проверить на равенство — это сравнить стек (^1..<?>..1$) с образцом (^1..<K>..1$).

Если предполагается, что глубина чтения/записи стека ограничена, то операция разового инкремента/декремента/сравнения с заданными числами реализуется введением промежуточных состояний (нетерминальных символов, которые живут только на вершине стека) — чтобы сделать последовательный инкремент-декремент-проверку.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, fAX, Вы писали:

К>>>Счетчиковый автомат в общем случае слабее стекового, поскольку он реализует стек из единичек.
fAX>>Я думал Вы имеете в виду добавить отнять произвольные числа (например, n = n + n).

К>Это не имеет значение. Добавить произвольное число K — это положить K фишек сверху.
К>Убавить — это снять.
К>Проверить на равенство — это сравнить стек (^1..<?>..1$) с образцом (^1..<K>..1$).
Но после такой проверки стек безвозвратно теряется.

К>Если предполагается, что глубина чтения/записи стека ограничена, то операция разового инкремента/декремента/сравнения с заданными числами реализуется введением промежуточных состояний (нетерминальных символов, которые живут только на вершине стека) — чтобы сделать последовательный инкремент-декремент-проверку.
Но нельзя динамически добавлять состояния, что рано или поздно придётся сделать, т.к. мы не можем запомнить содержание бесконечного стека в конечном состояний. Или я неправ?

Здравствуйте, fAX, Вы писали:

К>>Проверить на равенство — это сравнить стек (^1..<?>..1$) с образцом (^1..<K>..1$).
fAX>Но после такой проверки стек безвозвратно теряется.

См. ниже.

К>>Если предполагается, что глубина чтения/записи стека ограничена, то операция разового инкремента/декремента/сравнения с заданными числами реализуется введением промежуточных состояний (нетерминальных символов, которые живут только на вершине стека) — чтобы сделать последовательный инкремент-декремент-проверку.
fAX>Но нельзя динамически добавлять состояния, что рано или поздно придётся сделать, т.к. мы не можем запомнить содержание бесконечного стека в конечном состояний. Или я неправ?

Поскольку мы проектируем автомат, то еще на стадии создания выясняется, что нам потребуются
— проверки на N1, N2, ... — максимум на Nt
— прибавления и вычитания — максимум на Na.
Для простоты — максимальное число пусть будет N.

Теперь введем конечное число (порядка N^2) нетерминальных символов, в дополнение к символу "фишка" (1) и "дно" (0).
Стек всегда имеет вид
011...1F — с этой стороны вершина
Или, что то же самое, мы делаем стековый+конечный автомат.

Состояния, которые нам понадобятся:

Для вычитания k
0 Minus[k] --> облом!
1 Minus[k] --> Minus[k-1]

Для прибавления k
Plus[k] --> 1 Plus[k-1]
Plus[1] --> 1

Для сравнения с k
0 Test[k,0] --> 0 Equal[k,0]
0 Test[k,j] --> 0 Less[k,j]
1 Test[k,0] --> 1 Greater[k,0]

1 Test[k,j] --> Test[k,j-1]

Equal[k,k] --> ура!
Equal[k,j] --> 1 Equal[k,j+1]

и тому подобное

Естественно, мы считаем, что все эти нетерминалы более приоритетны, чем входные символы (т.е. пока автомат занимается проверкой, мы ничего нового не считываем).

ЗЫ
Программируем на Форте