Consider the following alphabet: sigma = {[0 0], [0 1], [1 0], [1 1]} Here, sigm

Question

Consider the following alphabet: sigma = {[0 0], [0 1], [1 0], [1 1]} Here, sigma contains all rows of 0s and Is of size 1 (one row). A string of symbols in sigma gives two columns of 0 and 1's. Consider each column to be part of a binary number, that is, all the first columns form a binary number and all the second columns form the other binary number. Let L= {w sigma*| the binary number formed by the last columns of w is twice the binary number formed by the first columns} For example: w = [0 0] [0 1] [1 0] [0 0] L (because the first columns form the binary number 0010 = 2 and the second columns form the binary number 0100 = 4, and 4 is twice 2) while w = [0 0] [0 1] [1 0] [0 1] L (because the first columns form the binary number 0010 = 2 and the second columns form the binary number 0101 = 5, and 5 is not twice 2). Show that L is regular.

Explanation / Answer

import java.util.HashMap;
import java.util.Map;

public class Test {

   public static void main(String[] args) {

       int[][] matrix1 = {{0, 0}, {0, 1}, {1, 0}, {0, 0}};
      
       int[][] matrix2 = {{0, 0}, {0, 1}, {1, 0}, {0, 1}};

       Test test = new Test();
       test.chekMatrix(matrix1);
       test.chekMatrix(matrix2);

   }

   private void chekMatrix(int[][] matrix) {
      
       int row = matrix[0].length;
       int column = matrix.length;
      
       Map<String, String> map = new HashMap<String, String>();

       for(int i=0; i<row; i++) {
           StringBuilder sb = new StringBuilder();
           for(int j=0; j<column; j++) {
               sb.append(String.valueOf(matrix[j][i]));
              
           }
           map.put("column"+i, sb.toString());
       }
      
       String firstColumn = map.get("column0");
       String secondColumn = map.get("column1");
      
       int column1 = Integer.parseInt(firstColumn, 2);
       int column2 = Integer.parseInt(secondColumn, 2);
      
       if(2*column1 == column2) {
           System.out.println("W belongs to L");
       } else {
           System.out.println("W does not belongs to L");
       }
      
   }

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.