결정 문맥 자유 언어

Question

문제 : 문맥 자유 언어에 대한 정의

L< {0,1} init (L) = { u | u v ε L for some v in {0, 1}} 
If L { w | w is nonempty and has an equal number of 0's and 1's}, 
then init (L) is set of all binary strings? 

답변 :

init (L) is set of all binary strings including the null string 
but how to prove it? 

Answer 1

먼저 당신이 초기화 (L)의 사용자 정의에 *를 놓친 것 같아 :

를

...for some v in {0, 1}*} 

그리고 증명 : 임의의 문자열 u에 0과 1을 사용할 수있는 경우이를 anoth와 연결할 수 있습니다 어 문자열, 말하자면 w = uv에있는 0과 1의 총 수가 같아 지도록 (단순히 u의 끝에 0 또는 1을 놓치십시오). 그래서 {0,1} *의 문자열은 L의 접두어가 될 수 있으므로 init (L) = {0,1} *