Primeiros e siga Sets verificar simples gramática

Question

Eis algumas perguntas que eu tinha em um teste em uma classe e só quero verificar sua exatidão. Gramática:

S -> ABC
A -> df | epsilon
B -> f | epsilon
C -> g | epsilon

1). O conjunto de Sequência de B contém g e epsilon (V / F)? Ans: F. Não há epsilon nos sets seguintes, correto? (Só $ aka final da entrada)

2). O primeiro conjunto de S contém d, f, g, e epsilon (V / F)? Ans: T. Disse falso para este porque pensou Primeira (S) = Em primeiro lugar (A), que G não é uma parte de. Quem está correto?

Answer 1

1. Você está correto. Se epsilon está envolvido, ele será contabilizado no primeiro set, e não o conjunto de Sequência. Se é possível para a produção de acabar com a corda, então $ passa no set Siga, não epsilon.
2. O questionário está correto. A produção de S pode de facto começar com qualquer de d, f, e g, e que também pode ser iniciada com a cadeia vazia. Considere a seqüência de entrada g. Ele corresponde S, certo? Um é satisfeita pela cadeia vazia, B é satisfeita pela cadeia vazia, e C é satisfeita por g. Uma vez que A, B, e C são todos satisfeitos, S é satisfeita. O primeiro caractere consumida por S é g, então g deve estar em primeiro lugar (S).