cfgrep - Exercises

1. For this problem we consider the following two languages over {0,1} :

   A =

   even length palindromic bitstrings

   B =

   bitstrings describing left-first traversals of full binary trees

   The language A is clear. B is not as clear, so let me explain: A full binary tree is a tree containing at least one child, such that every node is either a leaf, or is "full" -so has both a left and right subtrees. A left-first traversal describes a bitstring as follows:
   • Start at root.
   • Visit left sub-tree and then right subtree.
   • When encountering a left child for the first time, print 0.
   • When encountering a right child for the first time, print 1.
   For example, the tree:

      / \
     /\ /\
    /\   /\
   /\ 
   

   is described by the bitstring 000011110101
   1. For each of the languages above, come up with a context free grammar.
   2. Use cfgrep to solve the following puzzle: The file searchfile.txt contains exactly one line whose bitstring is in A, and exactly one line whose bitstring is in B. What word occurs on each resulting line? Hint: Together they name the character origins in a recently released movie on DVD.
   SOLUTION
2. For this problem we consider the following three languages over {0,1}:

   C =

   0*1* - { 0 ⁿ 1 ⁿ | n ≥ 0 } ( the complement of 0 ⁿ 1 ⁿ in 0*1* )

   D =

   bitstrings with more 1's than 0's

   E =

   { ( 0∪ 1) ^m 0( 0∪ 1) ^m (0∪ 1) ⁿ 0( 0∪ 1) ⁿ | m, n ≥ 0 }

   F =

   bitstrings that are not of the form ww. (Hint: play around with your grammar for E)

   1. For each of the languages above, come up with a context free grammar.
   2. For each of the languages C, D, E, F use cfgrep to count the number of 16-bit substrings that are in that language. Here's a file containing all length 16 bit-strings listed on separate lines.
   3. Use cfgrep to solve the following puzzles: For each language C, D, E, F there is a file which contains exactly one line in the given language. What was the unique matching bitstring? Write the cfgrep command you used to find the string. Here are the files that you are supposed to search through
      • Find the unique line in C contained in this file.
      • Find the unique line in D in this file.
      • Find the unique line in E in this file.
      • Find the unique line in F in this file.
   SOLUTION
3. Consider the languages G, H, I defined by:

   G =

   { 0ⁱ1^j0^k   |   i = j or j = k where i,j,k ≥ 0 }

   H =

   { 0ⁱ1^j   |   at least one quarter of the bits are 0 and at least one quarter are 1's }

   I =

   even length strings that are palindromic except at exactly one bit = { uAvv^RBu^R   |   u, v are arbitrary, and A, B are opposite bits }

   Use cfgrep to solve the following puzzle: A secret message has been hidden via a file containing all length 16 bitstrings, and a code book. The message consists of three words. To discover the first word do the following:
   • count the number of length-16 bitstrings which are in G and call this value n
   • go to line n in the code book, and find the revealed word
   For example, supposing there were 41,382 length-16 bitstrings which are in G, you would discover the word "whale" (not surprising in this Moby Dick based text). To discover the second word use the same method, but start from the set H. Similarly, you discover the third word by applying the method to I. You should write down the cfgrep commands used, the number of matches found (use the -c flag), and the final discovered message.

   HINTS:

   • The message reflects Zeph's opinion about the course.
   • Also, note that cfgrep differs from egrep in that the default behavior is matching the entire line. Thus you don't use ^ at the beginning or $ at the end of your expression.
   • cfgrep may give incorrect results if you use epsilons. I suggest getting rid of any epsilons for your cfgrep expression (this shouldn't affect the solutions because we aren't trying to match any empty strings).
   SOLUTION