Sardar Patel University 2008 B.E Computer Science CP201-Introduction to Theoretical (Internal Test) - Question Paper
Tuesday, 29 January 2013 11:00Web
Page 3 of 4
Marking Strategy:
1. For every accurate truth table 0.5 marks.
[B] 1) In the subsequent let {A, B, C, S} be the set of nonterminals, with S being the starting symbol. Let {a, b, c} be the set of terminals. define the language specified by set of productions verbally as well as in set-theoretic notations. (Any one)
(c) {S?AB, A?aA, A?a, B?Bb, B?b}
(d) {S?aA, A?bA, A?bC, C?cC, C?c} [2]
Ans. {S?AB, A?aA, A?a, B?Bb, B?b}
Language generated by grammar rules is:
L = { ai bj | i >= 1, j >=1}
OR
{S?aA, A?bA, A?bC, C?cC, C?c}
Language generated by grammar rules is:
L = { a bi cj | i >=1, j >=1}
Marking Strategy:
1. If accurate set theoretic notation then 2marks.
2) Give the grammar that specifies the subsequent language. (Any one)
(c) L={ai bj cq | i+j=q, i>=1, j>=1}
(d) L={a2i c b2j+1 | i>=1, j>=1} [2]
Ans. a) L={ai bj cq | i+j=q, i>=1, j>=1}
First we obtain which kind of strings are generated in the language:
L = { abcc, aabccc, abbccc, abbbccc… }
Grammar rule for the above language:
S ? aSc
S ? aBc
B ? bBc
B ? bc
OR
b) L={a2i c b2j+1 | i>=1, j>=1}
First we obtain which kind of strings are generated in the language:
L = { aacbbb, aaaacbbb, aaaacbbbbb…}
Grammar rule for the above language:
S ? AB
S ? Bbb | cbbb
A ? aaA | aa
Marking Strategy:
1. If all the rules are written correctly then two marks.
3) Consider the grammar in which N={signed_interger,sign, integer,digit} and T={+, -, 0, 1} with signed_integer being the starting symbol. Let the set of productions be:
signed_interger ? sign integer
sign ? +
sign ? -
integer ? digit integer
integer ? digit
digit ? 0
digit ? 1
Show the derivation of the string -010 in the language. [1]
Ans. signed_interger ? sign integer
? - digit integer
? - 0 digit integer
? - 0 0 digit
? - 0 one 0
Marking Strategy:
1. If all the steps are accurate shown then one mark.
Q-2 Attempt following:
[A] 1) Consider the experiment of tossing a fair coin until 2 heads or 2 tails appears in succession.
(c) Describe the sample space.
(d) What is the probability that the experiment ends before the 6th toss?
Earning: Approval pending. |