我可以使用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识别。但是，有些是，可以。