我可以使用DFA來跟蹤某些語言的字符串嗎？

Question

通常，DFA用於檢查給定的字符串是否以某種語言存在。 例如_ab1c存在於C中的變量語言中。

我在做什麼？ 但正如this question說，我使用的DFA跟蹤所有註釋，字符串等

如何我做的？ 考慮在給定的字符串/程序中跟蹤//註釋的示例。

static int makeTransition[][] = { 
     /*  Transition Table  */ 
       /*{other,\n, \, /, *, ', "} */ 
      /*q0*/ { 0, 0, 0, 1, 0, 0, 0}, 
      /*q1*/ { 0, 0,-1, 2, 0, 0, 0}, 
      /*q2*/ { 2, 0, 2, 2, 2, 2, 2}, 
     }; 

對於這一點，如果我有，

void assignPointerValuesInPairs(int index) 
    { 
/*comments is an ArrayList 
before marking start hotpointer = -1 
after marking start hotpointer = 0 
after marking end hotpointer is resetted to -1*/ 
     switch(currentState) 
      { 
      case 2:  /*q2*/ 
         comments.add(/*mark start*/); 
         hotPointer = 0; 
         break; 
      case 0: /*On initial state q0*/ 
       switch(hotPointer) 
       { 
       case 0: //If I am in end of comment. 
        comments.add(/*mark end*/);        
        hotPointer = -1; //Resetting the hotPointer. 
          break; 

       case -1: /*Already in q1 only*/ 
        /*Do nothing*/ 
       } 
     } 
    } 

public static void traceOut(String s) //entire program is accepted as string. 
    { 
      int index = 0; 
     while (index < s.length()) {     
         char c = s.charAt(index); 
         try{ 
      currentState = makeTransition[currentState][symbolToInteger(c)]; 
       if(currentState == -1) 
       throw new InvalidSyntaxException(); 
        } 
       catch(InvalidSyntaxException e){ 
       currentState = 0; 
       invalidSyntax.add(index);      
       } 
       assignPointerValuesInPairs(index); 
       index++;  
      } 



       currentState = 0; 
       assignPointerValuesInPairs(index); //These 2 statements help to color while typing.. (i.e) It forces the current state to get finished abruptly. 
     } 

} 

我的問題是...

我可以使用DFA，以紀念結束，在此//註釋的開始這樣， 或我也要跟着喜歡CFG等其他方式..

即

我的聲明：我可以使用DFA，不僅可以檢查特定的語言，還可以 在給定的 字符串中跟蹤某些字符串屬於某些語言。 （證明：按上述方法）。

我的上述陳述是否正確？

Answer 1

我的聲明：我可以使用DFA，不僅可以檢查特定的語言，還可以查找特定字符串中屬於某些語言的某些字符串。

我的上述陳述是否正確？

您的陳述非常正確。 某些語言可以使用DFA檢查。 （證明是存在的。如果任何這樣的語言存在，那麼你的說法是正確的，而且語言

 <program> ::= 'A' 

是一個簡單的例子，以滿足生存證明。）

但是，這是不是一個特別有用的陳述，因爲它沒有說明什麼種可以使用DFA檢查語言。

例如，如果您的評論語言支持嵌套註釋塊（如某些歷史編程語言所做的那樣），則DFA將無法工作。

您的陳述忽略的第二點是針對給定語言使用DFA是否爲實際。對於語法中所有形式的嵌套/遞歸的語言等，你理論上可以把語法翻譯成單一的有限DFA。但是，DFA會非常大，以至於無法實現。

（旁白 - 沒有現代的編程語言有這樣的界限在語法層面......不，這個問題是專門關於編程語言）

Answer 2

你需要更多的狀態。您的DFA違反多行評論。我很確定你確定你沒有意識到*/的「評論結束」序列。

是的，DFA可以識別這些類型的評論。容易。

最常見的編程語言不是常規語言，並且不能被DFA識別。但是，有些是，可以。