Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Задача про регулярные грамматики [D7, WinXP]

Страницы: < 1 2
Ozone © (2004-09-28 08:03:00)
Есть такое задание:

Написать программу, которая по заданной КС-грамматике будет генерировать цепочки языка (исп. только левосторонний или правосторонний вывод). Диапозон длин генерируемых цепочек должен задаваться пользователем.

ЗЫ: пользователь вводит состояния и правила для них

Я использовал в своей программе след. упрощенную структуру

{ Правило } TCross = record data: string; // символы indx: integer; // куда указывает end; { Состояние } TState = record Name : string[1]; // Имя A..Z Cross: array of TCross; // массив правил CCount: integer; // кол-во правил end; States : array of TState;

Собственно генератор я ужо написал... остается одна проблема.

К примеру, есть такая грамматика:
E = {0,1}; N = {S,A}
P:
S -> 1A
A -> 0A | 1111

Пользователь ввел кол-во цепочек = 5 и длину от 3 до 4 => ни одной такой цепочки не найдется... Как решить проблему?

У меня поиск (подбор) идет обычным рандомом, т.е. начанию с начального состояния (S) и двигаюсь дальше (рандомом) пока не дойду до терминального символа => как только дошел, проверяю попадает ли получившаяся цепочка в заданный диапазон.

Думаю смысл вопроса понятен... Есть идеи?

Defunct (2004-09-28 11:12:00) [21]
> 9. i := States[i].Cross[indx].indx;

у последнего правила индекс - (-1) я верно понял?

> 1. Можно ли улучшить алгоритм поиска.
а нужно ли? ну раз пользователь ввел недостаточно правил для формирования цепочки, то это его проблема. Причем тут ваш алгоритм.

> 2. Как узнать min длину цепочки.
мин длинна цепочки = min(legths( Data 0,j)), где j от 1 до CrossesCount в состоянии States[0]. (грубо говоря наименьшая по длине одна единица данныхпервого состояния и есть ваша возможная min цепочка по вашему алгоритму)

Можно начальное состояние задавать случайно.

Ozone (2004-09-28 10:41:00) [22]
Хммм... Попробую еще раз....

Есть произвольная регулярная грамматика G = {E, N, P, S}, где
E - множество символов алфавита грамматики
N - множество состояний
P - множество правил
S - начальное состояние.

Саму грамматику пользователь задает в форме Бекуса-Наура (т.е. не метасимволами и не графически, а набором правил для каждого состояния).

Введенные им (user'ом) правила я храю в массиве States описанном выше. Для генерации цепочек языка данной грамматики использую следующий алгоритм:
1. User задает нужное кол-во цепочек CHCount и диапазон длин цепочек
2. Count = 0 { кол-во найденых цепочек }
3. IF Count = CHCount THEN EXIT;
4. tmp := ''; // цепочка
5. Начинаю с начального состояния S => I := 0;
6. IF I < 0 THEN GOTO 11 {нашли терминал}
7. indx = random(States[i].CCount) {random'ом выбираем правило}
8. tmp := tmp + States[i].Cross[indx].data;
9. i := States[i].Cross[indx].indx;
10. GOTO 6
11. Проверяем "нужна" ли нам получившаяся цепочка
12. IF Нужна THEN inc(Count), GOTO 3 ELSE Goto 5

Вот... Можно наверно конкретизировать вопросы:
1. Можно ли улучшить алгоритм поиска
2. Как узнать min длину цепочки.

Defunct (2004-09-28 10:18:00) [23]
[3] И это называется пояснение?

http://ln.com.ua/~openxs/articles/smart-questions-ru.html

Ozone (2004-09-28 09:58:00) [24]
Defunct © (28.09.04 09:50) [2]

Ok. Поясняю.

//E = {0, 1}, что такое E? как трактовать {} - коментарий или
//множество? что такое 0, 1?

E - множество символов грамматики
0,1 - символы

// Что такое N, S и A?

N - множество состояний

// Что такое 0A | 1111?

Правила.

// Что такое 1A, почему, например, не 1И?

Потому что состояние "И" не задано.

Что у вас обозначает знак "->" - "эквивалентно" или просто от фонаря поставили?

Символ "->" означает что дальше идут правила для данного состояния.

// что-то тут рандомом и не пахнет. рандомом выбирается индекс
// или дельта индекса?

Так и есть - рандомом выбирается индекс правила для текущего состояния.

Defunct (2004-09-28 09:50:00) [25]
> Думаю смысл вопроса понятен...

3 раза перечитал - не понял.

E = {0, 1}, что такое E? как трактовать {} - коментарий или множество? что такое 0, 1?

Что такое N, S и A?
Что такое 0A | 1111?
Что такое 1A, почему, например, не 1И?
Что у вас обозначает знак "->" - "эквивалентно" или просто от фонаря поставили?

Вы думаете тут собрались телепаты, которые спят и видят вашу проблему?

> У меня поиск (подбор) идет обычным рандомом,

поиск(подбор) чего?

" обычным рандомом" - т.е. начанию с начального состояния(S) и двигаюсь дальше (рандомом) пока не дойду до терминального символа

что-то тут рандомом и не пахнет. рандомом выбирается индекс или дельта индекса?

> Пользователь ввел кол-во цепочек = 5 и длину от 3 до 4 => ни одной такой цепочки не найдется... Как решить проблему?

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

Хотите получить нормальный ответ, задайте нормальный (читать понятный всем) вопрос.

Ozone (2004-09-28 09:34:00) [26]
UP

Страницы: < 1 2

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »