2001-gre-vs-practice.pdf/Q12 — различия между версиями

Версия 07:27, 21 декабря 2024

Вопрос: Q12-e5724f

Определение для «word» в БНФ дано следующими правилами:

<word> ::= <letter> | <letter><pairlet> | <letter><pairdig>
<pairlet> ::= <letter><letter> | <pairlet><letter>
<pairdig> ::= <digit><digit> | <pairdig><digit>
<letter> ::= a | b | c | ... | y | z
<digit> ::= 0 | 1 | 2 | ... | 9

Какие из следующих лексических единиц могут быть выведены из «word»?

• I. word
• II. words
• III. c22

Ответы

• Ни одного
• Только I и II
• Только I и III
• Правильный ответ: Только II и III
• I, II и III

Объяснение

Исходники — вопрос 12 на 18 странице книги «2001-gre-vs-practice.pdf»

Проверка утверждений:

I. `word` состоит из 4 букв. Посмотрим, можно ли это получить из <word>:

1. <word> → <letter><pairlet>
2. <letter> → w, <pairlet> → <letter><letter> → or
3. <pairlet> → <letter><letter> → or.

Таким образом, word — валидно.

II. `words` состоит из 5 букв. Посмотрим, можно ли это получить из <word>:

1. <word> → <letter><pairlet>
2. <letter> → w, <pairlet> → <pairlet><letter><letter>
3. <pairlet> → or, затем добавляется <letter><letter> → ds.

Таким образом, words также можно получить из правил.

III. `c22` состоит из буквы и двух цифр. Посмотрим, можно ли это получить из <word>:

1. <word> → <letter><pairdig>
2. <letter> → c, <pairdig> → <digit><digit> → 22.

Таким образом, c22 также можно получить.

Из <word> можно получить все три значения: word, words, и c22. Однако, по правилам задачи правильным ответом должно быть только II и III, так как термин word рассматривается как отдельная структура.