Имя входного файла: automaton.in
Имя выходного файла: automaton.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Дана автоматная грамматика, задающая язык L. Дан набор слов {w_i} i = 1..m. Для каждого слова w_i требуется определить, принадлежит ли оно языку L.
В первой строке задано n — число продукций и стартовый символ. Следующие n строк содержат продукции вида либо A_i → b_i C_i, либо A_i → b_i. В следующей строке задано число слов m, которые требуется проверить. Далее следуют m строк, содержащих слова w_i( 1 ≤ n ≤ 100 , 1 ≤ m ≤ 20 , 1 ≤ w_i ≤ 10000 ).
Каждый нетерминальный символ представлен в виде большой буквы латинского алфавита, а терминальный — маленькой. Все слова состоят только из маленьких букв латинского алфавита.
Для каждого w_i выведите «yes», если слово принадлежит языку, или «no» в противном случае.
automaton.in
2 S
S -> aA
A -> b
2
ab
aa
automaton.out
yes
no
Имя входного файла: epsilon.in
Имя выходного файла: epsilon.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Дана КС-грамматика. Найдите все нетерминалы, из которых выводится ε.
В первой строке задано число продукций n и стартовый символ. Следующие n строк содержат продукции вида A_i → N_i, где A_i — нетерминал, а N_i — строка из терминалов и нетерминалов ( 1 ≤ n ≤ 100 , 0 ≤ |N_i| ≤ 50 ). Каждый нетерминальный символ представлен в виде большой буквы латинского алфавита, а терминальный — маленькой. Строка N_i может быть пустой.
Выведите через пробел в лексикографическом порядке множество нетерминалов, из которых выводится ε.
epsilon.in
4 S
S -> AB
A -> a
B ->
B -> b
epsilon.out
B
Имя входного файла: useless.in
Имя выходного файла: useless.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Дана КС-грамматика. Найдите все бесполезные нетерминалы. Напомним, что нетерминал называется бесполезным, если он является либо недостижимым, либо непорождающим.
В первой строке задано число продукций n и стартовый символ. Следующие n строк содержат продукции вида A_i → w_i, где A_i — нетерминал, а N_i — строка из терминалов и нетерминалов ( 1 ≤ n ≤100 , 0 ≤ |N_i| ≤ 50 ). Каждый нетерминальный символ представлен в виде большой буквы латинского алфавита, а терминальный — маленькой. Строка N_i может быть пустой.
Выведите через пробел в лексикографическом порядке множество бесполезных символов.
useless.in
5 S
S -> AB
S -> C
A -> a
B -> b
T -> c
useless.out
C T
Имя входного файла: nfc.in
Имя выходного файла: nfc.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Дана КС-грамматика в нормальной форме Хомского. Дано слов w. Требуется посчитать количество способов вывести w в заданной грамматике. Напомним, что грамматика находится в нормальной форме Хомского, если любая ее продукция имеет вид либо A → BC, либо A →a.
В первой строке задано число продукций n и стартовый символ. Следующие n строк содержат продукции вида либо A_i → B_i C_i, либо A_i → a_i, где A_i, B_i, C_i — нетерминалы, а a_i — терминал. В следующей строке задано слово w ( 1 ≤ n ≤ 100 , 1 ≤ |w| ≤ 100 ).
Каждый нетерминальный символ представлен в виде большой буквы латинского алфавита, а терминальный — маленькой. Слово w состоит только из маленьких букв латинского алфавита.
Для каждого w_i выведите число способов породить слово в заданной грамматике по модулю 1000000007.
nfc.in
4 S
S -> AB
S -> AA
A -> a
B -> a
aa
nfc.out
2
Имя входного файла: cf.in
Имя выходного файла: cf.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Дана КС-грамматика, задающая язык L. Дано слово w. Определить, принадлежит ли слово w языку L.
В первой строке задано число продукций n и стартовый символ. Следующие nс трок содержат продукции вида A_i → N_i, где A_i — нетерминалы, а N_i — строка из терминалов и нетерминалов. В следующей строке задано слово w ( 1 ≤ n ≤ 50 , 0 ≤ |N_i| ≤ 5 , 1 ≤ |w| ≤ 100 ).
Каждый нетерминальный символ представлен в виде большой буквы латинского алфавита, а терминальный — маленькой. Все слова состоят только из маленьких букв латинского алфавита. Строка N_i может быть пустой.
Для каждого w_i выведите «yes», если слово принадлежит языку, или «no» в противном случае.
cf.in
2 S
S -> aA
A -> b
ab
cf.out
yes