2
주어진 정규 표현식 (RE)을 왼쪽 (또는 오른쪽) 선형 문법으로 변환하는 표준 알고리즘은 무엇입니까?정규 표현식을 선형 문법으로 변환하는 알고리즘
은 내가 (RE에서 선형 문법을 작성하는) 이런 식으로이 작업을 수행 할 수 있습니다 알고
RegEx -> NFA -> DFA -> Right Linear grammar.
직접 접근을 위해 (0 + 10)*과 같은 간단한 정규식을 처리하고 선형 문법을 만들 수 있습니다.
그러나 중첩 된 kleene star가있는 경우 잘 정의 된 메서드없이 선형 인 CFG를 만드는 것이 정말 어렵습니다.
비슷한 질문에 대한 답변을 here 및 here으로 보았습니다. 그러나 그들은 일반적인 알고리즘을 제공하지 않거나 정규 표현식을 linear 문법으로 변환하지 않습니다.
특히 알고리즘을 사용하여 (((01+10)*00)*11)*을 선형 문법으로 직접 변환 하시겠습니까?
도움을 주시면 감사하겠습니다.
편집은 좀 더 검색을했다. 그리고 이걸 얻었 어.
Constructing an Equivalent Regular Grammar from a Regular Expression
http://www-cs.ccny.cuny.edu/~vmitsou/304spring10/slides/lineargrammars.pptx http://www-cs.ccny.cuny.edu/에서 ~ vmitsou/304spring10/sched.html이 질문에 대한 대답 인 것 같습니다. – nhahtdh
안녕하세요 당신의 제안은 [내 대답은 여기에] 맞았 어 (http://stackoverflow.com/questions/13816439/left-linear-and-right-linear-grammars?answertab=votes#tab-top) 나는 바보 같은 실수를 저질 렀다. . 하지만 편집을 승인하기 전에 다른 사용자가 거부합니다. 이제 나는 내 대답을 바로 잡았습니다. 다시 한 번 확인하여 새로운 도움을 얻을 수 있도록 요청하십시오. 저녁 시간에이 질문에 당신을 도울 수 있습니다 ... 고마워요 !! –
간단히 말해 RE에서 선형 문법 (LG)에 대한 표준 알고리즘 *을 사용할 수 있습니다. RE에서 DFA 알고리즘에 이르기까지 두 단계로 진행됩니다. 그런 다음 DFA를 LG 알고리즘 방식으로 실행합니다 (** 두 가지 알고리즘 **을 검색합니다). 행운이지만 정규 언어에 대한 정규 표현식 정규 표현식과 문법은 같은 목적으로 사용되었지만 다른 일반 언어에 대해서는 정규 표현식 유형의 메커니즘이 없으므로 언어를 표현할 수있는 메커니즘이 없습니다. 네, RL에는 문법과 문법이 모두 있습니다. –