Hamming single-error-correcting-code

Problem : Hamming single-error-correcting-code

The Hamming single-error-correcting code requires approximately log2(N) check bits to correct single-bit errors. Start by renumbering the data bits with indices that aren't powers of two:

Indices for 16 data bits = 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21

The idea is to compute the check bits choosing subsets of the data in such a way that a single-bit error will produce a set of parity errors that uniquely indicate the index of the faulty bit:

p0 = even parity for data bits 3, 5, 7, 9, 11, 13, 15, 17, 19, 21
p1 = even parity for data bits 3, 6, 7, 10, 11, 14, 15, 18, 19
p2 = even parity for data bits 5, 6, 7, 12, 13, 14, 15, 20, 21
p3 = even parity for data bits 9, 10, 11, 12, 13, 14, 15
p4 = even parity for data bits 17, 18, 19, 20, 21

Note that each data bit appears in at least two of the parity calculations, so a single-bit error in a data bit will produce at least two parity errors. When checking a protected data field, if the number of parity errors is zero or one, the data bits are okay (exactly one parity error indicates that one of the parity bits was corrupted). If two or more parity errors are detected then the errors identify exactly which bit was corrupted.

A.   What is the relationship between the index of a particular data bit and the check subsets in which it appears? Hint: consider the binary representation of the index.

Digit i in the binary expansion of a data bit index indicates whether the index should be included in the calculation of pi. For example, the first data bit (which has index 3 = 00011) would be used in the parity calculation for parity bits p0 and p1. Likewise, the sixth data bit (which has index 10 = 01010) would be used in the parity calculation for parity bits p1 and p3. Since no data bit is assigned an index which is a power of two, we guarantee that each data bit is used in the calculation of at least two different parity bits.

B.    If the parity calculations involving p0, p2 and p3 fail, assuming a single-bit error what is the index of the faulty data bit?

We need to find the data index that appears in the calculation p0, p2 and p3 but not in the calculations for p1 and p4. Indicies 13 and 15 appear in p0, p2 and p3, but index 15 appears in the calculation for p1. So the index of the data bit that failed is 13.

We can construct the index of the failing data bit directly from the parity calculations using ei = 1 if the pi failed and ei = 0 if it didn't. So if p0, p2 and p3 failed, and the others didn't, the index is e4e3e2e1e0 = 01101 = 13₁₀.

C.    The Hamming SECC doesn't detect all double-bit errors. Characterize the types of double-bit errors that will not be detected. Suggest a simple addition to the Hamming SECC that allows detection of all double-bit errors.

If errors occur in two separate parity bits, this will be misinterpreted as a single data bit error. Also when certain pairs of data bits have errors, the double-bit error masquerades as a single-bit error in another, unrelated bit (e.g., suppose bits with indicies 19 and 21 both have errors).

We can detect these situations by adding an additional parity bit, p5, which is the parity of all other parity and data bits. If a single data bit failed, this bit would indicate and error. But if exactly two bits have failed, p5 would indicate no error, but p0, p1, ..., p4 would indicate the presence of some error (although the indication might point at the wrong data bit). So, if by looking at p0, p1, ..., p4 it seems as though an error occurred, we should check p5 to make sure that only one error occurred. If p5 does not indicate an error, then a double-bit error occurred.

Error detection and correction

Problem : Error detection and correction

A.   To protect stored or transmitted information one can add check bits to the data to facilitate error detection and correction. One scheme for detecting single-bit errors is to add a parity bit:

b₀ b₁ b₂ b_N-1 p

When using even parity, p is chosen so that the number of "1" bits in the protected field (including the p bit itself) is even; when using odd parity, p is chosen so that the number of "1" bits is odd. In the remainder of this problem assume that even parity is used.

To check parity-protected information to see if an error has occurred, simply compute the parity of information (including the parity bit) and see if the result is correct. For example, if even parity was used to compute the parity bit, you would check if the number of "1" bits was even.

If an error changes one of the bits in the parity-protected information (including the parity bit itself), the parity will be wrong, i.e., the number of "1" bits will be odd instead of even. Which of the following parity-protected bit strings has a detectable error?

(1) 11101101111011011
(2) 11011110101011011
(3) 10111110111011110
(4) 00000000000000000

Strings 1 and 3 have detectable errors. Note that parity allows one to detect single-bit errors (actually any odd number of errors) but doesn't defend against an even number of bit errors.

B.    Detecting errors is useful, but it would also be nice to correct them! To build an error correcting code (ECC) we'll use additional check bits to help pinpoint where the error occurred. There are many such codes; a particularly simple one for detecting and correcting single-bit errors arranges the data into rows and columns and then adds (even) parity bits for each row and column. The following arrangement protects nine data bits:

C.  b0,0     b0,1    b0,2    prow0

D.  b1,0     b1,1    b1,2    prow1

E.  b2,0     b2,1    b2,2    prow2

F.  pcol0    pcol1   pcol2

A single-bit error in one of the data bits (b_I,J) will generate two parity errors, one in row I and one in column J. A single-bit error in one of the parity bits will generate just a single parity error for the corresponding row or column. So after computing the parity of each row and column, if both a row and a column parity error are detected, inverting the listed value for the appropriate data bit will produce the corrected data. If only a single parity error is detected, the data is correct (the error was one of the parity bits).

Give the correct data for each of the following data blocks protected with the row/column ECC shown above.

(1)  1011    (2) 1100    (3) 000    (4) 0111

     0110        0000        111        1001

     0011        0101        10         0110

     011         100                    100

(1)  0011    (2) 1100    (3) 000    (4) 0110

     0110        0000        101        1001

     0011        0101        10         0110

     011         100                    100

(1) and (3) had single bit errors, (2) had no detectable errors, and (4) had an error in a parity bit. The red digits represent corrected values.

C.    The row/column ECC can also detect many double-bit errors (i.e., two of the data or check bits have been changed). Characterize the sort of double-bit errors the code does not detect.

If parity bits detect an error for exactly one column and exactly one row, this will be interpreted as a single bit error in the corresponding data position. This can happen with two parity bit errors, one in each of the row and column check bits. The fact that two errors occurred is not detected; worse, the corresponding data position is changed from the correct value to the incorrect value.

D.   In the days of punch cards, decimal digits were represented with a special encoding called 2-out-of-5 code. As the name implies two out of five positions were filled with 1's as shown in the table below:

Code	Decimal
11000	1
10100	2
01100	3
10010	4
01010	5
00110	6
10001	7
01001	8
00101	9
00011	0

E.    What is the smallest Hamming distance between any two encodings in 2-out-of-5 code?

The Hamming distance between any two encodings is the number of bit positions in which the encodings differs. With this code, the smallest Hamming distance is 2.

F.    Characterize the types of errors (eg, 1- and 2-bit errors) that can be reliably detected in a 2-out-of-5 code?

Codes with a Hamming distance of 2 can detect 1-bit errors. The 2-out-of-5 code also detects 3-bit errors, but not 2-bit errors. Normally when we say a code detects n-bit errors we imply that it detects m-bit errors for m < n. Following this convention, we would say that the 2-out-of-5 code detects 1-bit errors.

G.   We know that even parity is another scheme for detecting errors. If we change from a 2-out-of-5 code to a 5-bit code that includes an even parity bit, how many additional data encodings become available?

There are 16 possible values for the 4 data bits in the 5-bit parity encoding, six more than the 10 possible values in the 2-out-of-5 code.

Variable-length encoding

Problem : Variable-length encoding

After spending the afternoon in the dentist's chair, Ben Bitdiddle has invented a new language called DDS made up entirely of vowels (the only sounds he could make with someone's hand in his mouth). The DDS alphabet consists of the five letters "A", "E", "I", "O", and "U" which occur in messages with the following probabilities:

Letter	Probability of occurrence
A	p(A) = 0.15
E	p(E) = 0.4
I	p(I) = 0.15
O	p(O) = 0.15
U	p(U) = 0.15

A.   If you are told that the first letter of a message is "A", give an expression for the number of bits of information have you received.

Using the formula given in lecture, the number of bits of information is log₂(1/p(A)) = log₂(1/0.15)

B.    Ben is trying to invent a fixed-length binary encoding for DDS that permits detection and correction of single bit errors. Briefly describe the constraints on Ben's choice of encodings for each letter that will ensure that single-bit error detection and correction is possible. (Hint: think about Hamming distance.)

Each encoding must differ from other encodings in at least 3 bit positions, i.e., encodings must have a Hamming distance >= 3. This ensures that each received codeword (even those with single-bit errors) can be associated with a particular source encoding.

C.    Giving up on error detection and correction, Ben turns his attention to transmitting DDS messages using as few bits as possible. Assume that each letter will be separately encoded for transmission. Help him out by creating a variable-length encoding that minimizes the average number of bits transmitted for each letter of the message.

Using the simple "greedy" algorithm described above:

S = {A/0.15 E/0.4 I/0.15 O/0.15 U/0.15}

  arbitrarily choose O & U

  encoding: "0" => O, "1" => U

S = {A/0.15 E/0.4 I/0.15 OU/0.3}

  choose A & I

  encoding: "0" => A, "1" => I

S = {AI/0.3 E/0.4 OU/0.3}

  choose AI & OU

  encoding: "00" => A, "01" => I, "10" => O, "11" => U

S = {AIOU/0.6 E/0.4}

  choose E & AIOU

  encoding: "0" => E, "100" => A, "101" => I, "110" => O, "111" => U

S = {AEIOU/1.0}

Note that the assignments of symbols to encodings "0" and "1" were arbitrary and could have been swapped at each level. So, for example, swapping the encoding at the last step would have resulted in

  encoding: "1" => E, "000" => A, "001" => I, "010" => O, "011" => U

which achieves the same average bits/symbol as the previous encoding.

Variable length encoding & compression

Problem : Variable length encoding & compression

A.   Huffman and other coding schemes tend to devote more bits to the coding of

(A) symbols carrying the most information
(B) symbols carrying the least information
(C) symbols that are likely to be repeated consecutively
(D) symbols containing redundant information

Answer:

(A) symbols carrying the most information, i.e., the symbols that are less likely to occur. This makes sense: to keep messages as short as possible, frequently occuring symbols should be encoded with fewer bits and infrequent symbols with more bits.

B.    Consider the following two Huffman decoding tress for a variable-length code involving 5 symbols: A, B, C, D and E.

Using Tree #1, decode the following encoded message: "01000111101".

Answer:

To decode the message, start at the root of the tree and consume digits as you traverse down the tree, stopping when you reach a leaf node. Repeat until all the digits have been processed. Processing the encoded message from left-to-right:

"0" => A
"100" => B
"0" => A
"111" => E
"101" => C

C.    Suppose we were encoding messages that the following probabilities for each of the 5 symbols:

p(A) = 0.5
p(B) = p(C) = p(D) = p(E) = 0.125

Which of the two encodings above (Tree #1 or Tree #2) would yield the shortest encoded messages averaged over many messages?

Answer:

Using Tree #1, the expected length of the encoding for one symbol is:

1*p(A) + 3*p(B) + 3*p(C) + 3*p(D) + 3*p(E) = 2.0

Using Tree #2, the expected length of the encoding for one symbol is:

2*p(A) + 2*p(B) + 2*p(C) + 3*p(D) + 3*p(E) = 2.25

So using the encoding represented by Tree #1 would yield shorter messages on the average.

D.   Using the probabilities for A, B, C, D and E given above, construct a variable-length binary decoding tree using a simple greedy algorithm as follows:

1.     Begin with the set S of symbols to be encoded as binary strings, together with the probability P(x) for each symbol x. The probabilities sum to 1, and measure the frequencies with which each symbol appears in the input stream. In the example from lecture, the initial set S contains the four symbols and associated probabilities in the above table.

2.     Repeat the following steps until there is only 1 symbol left in S:

A.   Choose the two members of S having lowest probabilities. Choose arbitrarily to resolve ties. In the example aove, D and E might be the first nodes chosen.

B.    Remove the selected symbols from S, and create a new node of the decoding tree whose children (sub-nodes) are the symbols you've removed. Label the left branch with a "0", and the right branch with a "1". In the first iteration of the example above, the bottom-most internal node (leading to D and E) would be created.

C.    Add to S a new symbol (e.g., "DE" in our example) that represents this new node. Assign this new symbol a probability equal to the sum of the probabilities of the two nodes it replaces.

Answer:

S = {A/0.5 B/0.125 C/0.125 D/0.125 E/0.125}

  arbitrarily choose D & E

  encoding: "0" => D, "1" => E

S = {A/0.5 B/0.125 C/0.125 DE/0.25}

  choose B & C

  encoding: "0" => B, "1" => C

S = {A/0.5 BC/0.25 DE/0.25}

  choose BC & DE

  encoding: "00" => B, "01" => C, "10" => D, "11" => E

S = {A/0.5 BCDE/0.5}

  choose A & BCDE

  encoding: "0" => A, "100" => B, "101" => C, "110" => D, "111" => E

S = {ABCDE/1.0}

This Tree #1 shown in the diagram above. The choice of D & E as the first symbols to combine was arbitrary -- we could have chosen any two symbols from B, C, D and E. So there are many equally plausible encodings that might emerge from this algorithm, corresponding the interchanging B, C, D and E at the leaves of the tree.

E.    Huffman coding is used to compactly encode the species of fish tagged by a game warden. If 50% of the fish are bass and the rest are evenly distributed among 15 other species, how many bits would be used to encode the species of a bass?

Answer:

1 bit, using the algorithm described above.

F.     Consider the sum of two six-sided dice. Even when the dice are "fair" the amount information conveyed by a single sum depends on what the sum is since some sums are more likely than others, as shown in the following figure:

What is the average number of bits of information provided by the sum of 2 dice? Suppose we want to transmit the sums resulting from rolling the dice 1000 times. How many bits should we expect that transmission to take?

Answer:

Average number of bits = sum p_ilog₂(1/p_i) for i = 2 through 12. Using the probabilities given in the figure above the average number of bits of information provided by the sum of two dice is 3.2744.

So if we had the perfect encoding, the expected length of the transmission would be 3274.4 bits. If we encode each sum separately we can't quite achieve this lower bound -- see the next question for details.

G.   Suppose we want to transmit the sums resulting from rolling the dice 1000 times. If we use 4 bits to encode each sum, we'll need 4000 bits to transmit the result of 1000 rolls. If we use a variable-length binary code which uses shorter sequences to encode more likely sums then the expected number of bits need to encode 1000 sums should be less than 4000. Construct a variable-length encoding for the sum of two dice whose expected number of bits per sum is less than 3.5. (Hint: It's possible to find an encoding for the sum of two dice with an expected number of bits = 3.306.)

Answer:

Using the greedy algorithm given above, we arrive at the following encoding which has 3.3056 as the expected number of bits for each sum.

H.   Okay, so can we make an encoding for transmitting 1000 sums that has an expected length smaller than 3306 bits?

Answer:

Yes, but we have to look at encoding more than one sum at a time, e.g., by applying the construction algorithm to pairs of sums, or ultimately to all 1000 sums at once. Many of the more sophisticated compression algorithms consider sequences of symbols when constructing the appropriate encoding scheme.

Questions on Information

Problem : Measuring information

A.   Someone picks a name out of a hat known to contain the names of 5 women and 3 men, and tells you a man has been selected. How much information have they given you about the selection?

Answer: -

There are 8 names to start with and knowing the selection is a man narrows the choices down to 3 names. Using the formula from lecture with N = 8 and M = 3, we've been given log₂(8/3) bits of information.

Alternatively, the probability of drawing a man's name is p_man = 3/8, so the amount of information received is log₂(1/p_man) = log₂(1/(3/8)) = log₂(8/3).

B.    You're given a standard deck of 52 playing cards that you start to turn face up, card by card. So far as you know, they're in completely random order. How many new bits of information do you get when the first card is flipped over? The fifth card? The last card?

Answer: -

Before the first card was flipped over there are 52 choices for what we'll see on the first flip. Turning the first card over narrows the choice down to a single card, so we've received log₂(52/1) bits of information.

After flipping over 4 cards, there are 48 choices for the next card, so flipping over the fifth card gives us log₂(48/1) bits of information.

Finally if all but one card has been flipped over, we know ahead of time what the final card has to be so we don't receive any information from the last flip. Using the formula, there is only 1 "choice" for the card before the card is flipped and we have the same "choice" afterwards, so, we receive log₂(1/1) = 0 bits of information.

C.    X is an unknown N-bit binary number (N > 3). You are told that the first three bits of X of 011. How many bits of information about X have you been given?

Answer: -

Since we were told about 3 bits of X it would make sense intuitively that we've been given 3 bits of information! Turning to the formulas: there are 2^N N-bit binary numbers and 2^N-3 N-bit binary numbers that begin with 011. So we've been given log₂(2^N/2^N-3) = log₂(2³) = 3 bits of information (whew!).

D.  X is an unknown 8-bit binary number. You are given another 8-bit binary number, Y, and told that the Hamming distance between X and Y is one. How many bits of information about X have you been given?

Answer: -

Before we learn about Y, there are 2⁸ = 256 choices for X. If the Hamming distance between X and Y is one that means that X and Y differ in only one of their 8 bits, i.e., for a given Y there are only eight possible choices for X. So we've been given log₂(256/8) = 5 bits of information.

Information Theory and Coding

e-Notes	Topic	Subject Matter Experts
Click here	Entropy and rate of Information of an Information Source / Model of a Markoff Source	Prof. P S Sathyanarayan, BMSCE, B'lore Prof. M S Sudhi, MSRIT, B'lore Prof. B J Subbakrishna, NIE, Mysore
Click here	System Analysis with regard to Markoff sources
Click here	Entropy and Information Rate of Markoff Sources
Click here	Encoding of the Source Output
Click here	Operation of the Source Encoder Designed
Click here	SOURCE ENCODER DESIGN AND COMMUNICATION CHANNELS
Click here	ENTROPIES PERTAINING TO DMC
Click here	DISCRETE CHANNELS
Click here	CAPACITY OF A DMC
Click here	CONCEPTS OF ERROR CONTROL CODING -- BLOCK CODES
Click here	DISCRETE CHANNELS WITH MEMORY
Click here	INFORMATION THEORY AND SOURCE ENCODING

TOC mCQ Two

1.	Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE? P3 is decidable if P1 is reducible to P3 P3 is undecidable if P3 is reducible to P2 P3 is undecidable if P2 is reducible to P3 P3 is decidable if P3 is reducible to P2’s complement
2.	Consider three problems P1, P2 and P3. It is known that P1 has polynomial time solution and P2 is NP-complete and P3 is in NP. Which one of the following is true. P3 has polynomial time solution if P1 is polynomial time reducible to P3 P3 is NP complete if P3 is polynomial time reducible to P2 P3 is NP complete if P2 is reducible to P3 P3 has polynomial time complexity and P3 is reducible to P2
3.	Consider the FSA M The language recognized by M is {w ∊ {a, b}* | every a in w is followed by exactly two b’s} {w ∊ {a, b}* | every a in w is followed by atleast two b’s} {w ∊ {a, b}* |w contains the substring ‘abb’} {w ∊ {a, b}* |w does not contain ‘aa’ as substring}
4.	Let Nf and Np denote the classes of languages accepted by nondeterministic FSA and nondeterministic PDA, respectively. Let Df and Dp denote the classes of languages accepted by deterministic FSA and PDA respectively. Which of the following is TRUE? Some of these questions have appeared in GATE examinations. Df ⊂ Nf Dp ⊂ Np Df ⊂ Nf Dp = Np Df = Nf Dp ⊂ Np Df = Nf Dp = Np
5.	Consider the languages L1 = {anbncm|n, m > 0} and L2 = {anbmcm|n, m > 0} Which one of the following statements is false? L1 ∩ L2 is a CFL L1 ∪ L2 is a CFL L1 ∪ L2 is inherently ambiguous L1 ∩ L2 is a CSL
6.	Consider the languages L1 = {anbmcndp|n, m, p > 0} and L2 = {anbmcpdm|n, m, p> 0} Which one of the following statements is false? L1 ∩ L2 is a CFL L1 ∪ L2 is a CFL L1 ∪ L2 is inherently ambiguous L1 ∩ L2 is a CSL
7.	Consider the languages L1 = {anbmcmdn|n, m > 0} and L2 = {anbncmdm|n, m > 0} Which one of the following statements is false? L1 ∪ L2 is a CFL L1 ∩ L2 is a CFL L1 and L2 are CFL L1 ∩ L2 is a CSL
8.	Let L and be a language and its complement. Which one of the following possibilities will not hold? L and are recursive L is recursively enumerable but not recursive is not recursively enumerable L and are not recursively enumerable L and are recursively enumerable but not recursive
9.	Let L1 be a recursive language and let L2 be a recursively enumerable language which is not recursive. Which one of the following is TRUE? is recursive, is recursively enumerable. is recursive, is not recursively enumerable. and are recursively enumerable. is recursively enumerable and is recursive.
10.	Consider the languages L1 = {wwR|w ∊ {0,1}*} L2 = {wcwR|w ∊ {0,1}*} L3 = {ww|w ∊ {0,1}*} Which one of the following is TRUE? L1 is deterministic CFL L2 is deterministic CFL L3 is a CFL but not a deterministic CFL L3 is deterministic CFL
11.	Let S be a NP–complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which one of the following statements is TRUE? R is NP complete R is NP hard Q is NP complete Q is NP hard
12.	L1 = {an + m bn cm|n, m ≥ 0} L2 = {an + m bn + m cm|n, m ≥ 0} L3 = {an + m bn + m cm + n|n, m ≥ 0} Which of these languages are not CF. L1 only L3 only L1 and L2 L2 and L3
13.	If s is a string over (0+1)* then let m0 (s) denote the number of 0’s in s and n1 (s) the number of 1’s in s. Which one of the following languages is not regular? L = {s ∊ (0+1)*|n0(s) is a 3-digit prime} L = {s ∊ (0+1)*|for every prefix s′ of s, |n0 (s′) − n1(s′)| ≤ 2} L = {s ∊ (0+1)*‖n0(s) − n1(s)| ≤ 4} L = {s ∊ (0+1)*|n0(s) mod 7 = n1(s) mod 5 = 0}
14.	For s ∊ (0+1)*let d(s) denote the decimal value of s (eg. D(|0|) = 5). Let L = {s ∊ (0+1)*|d(s) mod 5 = 2 and d(s) mod 7 ≠ 4} Which one of the following statements is TRUE? L is recursively enumerable but not recursive L is recursive, but not context-free L is context-free, but not regular L is regular
15.	Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following is TRUE? Both FHAM and DHAM are NP-hard FHAM is NP hard, but DHAM is not DHAM is NP hard, but FHAM is not Neither FHAM nor DHAM is NP hard
16.	Consider the following statements about the context-free grammar G = {S → SS, S → ab, S → ba, S → c} G is ambiguous G produces all strings with equal number of a’s and b’s G can be accepted by a deterministic PDA Which combination below expresses all the true statements about G? I only I and III only II and III only I, II and III
17.	Let L1 be a regular language and L2 a deterministic CFL. L3 is recursively enumerable but not recursive. Which one of the following statement is FALSE? L1 ∩ L2 is a DCFL L3 ∩ L1 is recursive L1 ∪ L2 is context-free L1 ∩ L2 ∩ L3 is recursively enumerable
18.	Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting the language is 3 5 8 9
19.	Which one of the following grammars generates the language L = {aibj|i ≠ j}. S → AC|CB C → aCb|a|b A → aA|ε B → Bb|ε S → aS|Sb|a|b S → AC|CB C → aCb|ε A → aA|ε B → Bb|ε S → AC|CB C → aCb|ε A → aA|a B → bB|b
20.	In the above correct grammar what is the minimum length of the derivation (number of steps starting from S) to generate the string a1 bm with l ≠ m? max(l, m) + 2 l + m + 2 l + m + 3 max(l, m) + 3
21.	Consider S → SS|a. What is the number of different derivation trees for aaaaa 3 5 7 14
22.	Which one of the following grammar generates L = {ai bj ck|i ≠ k, i, j, k ≥ 1} S → AC|CB A → aA|a B → Bc|c C → aCc|bD|b D → bD|b S → aS|aA A → bA|bB B → cB|c S → AB A → aAb|ab B → bBc|bc S → AC|CB A → aA|ε B → Bc|ε C → aCc|ε|bD D → bD|b|ε
23.	A minimum state deterministic automaton accepting the language L = {w|w ∊ {0,1}*, the number of 0’s and 1’s in w are divisible by 3 and 5 respectively} has 15 states 11 states 10 states 9 states
24.	The language L = {0i21i / i ≥ 0} over the alphabet {0, 1, 2} is not recursive is recursive and is a deterministic CFL is a regular language is not a deterministic CFL but a CFL
25.	Which of the following languages is regular? {wwR|w ∊ {0, 1}+} {wwRx|w, x ∊ {0, 1}+} {w x w R|w, x ∊ {0, 1}+} {xwwR|w, x ∊ {0, 1}+}
26.	Let Σ = {0, 1}, L1 = Σ* and L2 = {0n 1n|n ≥ 1} then the languages L1 ∪ L2 and L2 are respectively regular, regular regular, not regular not regular, regular not regular, not regular
27.	Which of the following statements is false? The halting problem for Turing machines is undecidable determining whether a context-free grammar is ambiguous is un-decidable given two arbitrary context-free grammar, G1 and G2, it is undecidable with L(G1) = L(G2) given two regular grammars G1 and G2, it is undecidable whether L(G1) = L(G2)
28.	Two of the following four regular expressions are equivalent. Which two? (00)* (0 + ε) (00)* 0* 0(00)* (i) and (ii) (ii) and (iii) (i) and (iii) (iii) and (iv)
29.	Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true? L = {x|x has an equal number of a’s and b’s } is regular L = {an bn | n ≥ 1} is regular L = {am bn | m, n ≥ 1} is regular L = {x|x has more a’s than b’s} is regular
30.	Define for a CFL L, init (L) = {u | uv ∊ L for some v ∊ {0, 1}*}. In other words init (L) is the set of prefixes of L. Let L = {w|w ∊ {0, 1}+, w has equal number of 0’s and 1’s}. Then init (L) is the set of all binary strings with unequal number of 0’s and 1’s the set of all binary stings including ε the set of all binary strings with exactly one more 0 than the number of 1’s or one more 1 than the number of 0’s. none of the above
31.	If L1 and L2 are CFL and R a regular set, one of the languages below is not necessarily a CFL. Which one? L1L2 L1 ∪ L2 L1 ∩ L2 L1 ∩ R
32.	The grammar whose productions are 〈stmt〉 → if 〈id〉 then 〈stmt〉 〈stmt〉 → if 〈id〉 then 〈stmt〉 else 〈stmt〉 〈stmt〉 → 〈id〉 := 〈id〉 〈id〉 → a|b|c|d|f is ambiguous because the sentence if a then if b then c := d has more than one derivation trees the leftmost and rightmost derivation of the sentence if a then if b then c := d give rise to different parse trees the sentence if a then if b then c := d else c := f has more than two parse trees the sentence if a then if b then c := d else c := f has two parse trees
33.	Which one of the following regular expressions over {0, 1} denotes the set of all strings not containing 100 as a substring? 0*(11*0)* 0*1010* 0*1*01 0*(10 + 1)*
34.	Which one of the following is not decidable? given a Turing machine M, a string s, and an integer k, M accepts s with k steps equivalence of two given Turing machines language accepted by a given DFSA is nonempty language generated by a CFG is nonempty
35.	Which of the following languages over {a, b, c} is accepted by a deterministic PDA? {wbwR|w ∊ {a, c}*} {wwR|w ∊ {a, b, c}*} {anbncn|n ≥ 1} {w|w is a palindrome over {a, b, c}}
36.	Which of the following instances of the post correspondence problem has a viable sequence (a solution)? {(b, bb), (bb, bab), (bab, abb), (abb, babb)} {(ab, aba), (baa, aa), (aba, baa)} {(ab, abb), (ba, aaa), (aa, a)} none of the above
37.	It is undecidable, whether an arbitrary TM has 15 states an arbitrary TM halts after 10 steps an arbitrary TM ever prints a specific letter an arbitrary TM accepts a string w in 5 steps
38.	Let r = 1(1+0)*, s = 11*0 and t = 1*0 be three regular expressions and R, S, T the regular sets corresponding to them. Which of the following is true? S ⊂ R R ⊂ S T ⊂ S R ⊂ T
39.	Which one of the following is the strongest correct statement about a finite language L over a finite alphabet Σ? L is undecidable L is recursive L is a CSL L is a regular set
40.	Which of the following statements is TRUE? infinite union of regular sets is regular infinite union of finite sets is regular finite union of finite sets is regular complement of a finite set need not be regular Answers 1. c 2. c 3. b 4. c 5. a 6. a 7. b 8. d 9. b 10. b 11. b 12. d 13. c 14. d 15. a 16. b 17. b 18. d 19. a 20. a 21. d 22. a 23. a 24. b 25. c 26. b 27. d 28. c 29. c 30. b 31. c 32. d 33. d 34. b 35. a 36. c 37. c 38. a 39. d 40. c