์ ๊ท ํํ์์ ๋ณด๋ ํ ๊ฐ์ง ๋ฐฉ๋ฒ์ ๋ค์ ์ฌ์ค์ ๋ํ ๊ฑด์ค์ ์ธ ์ฆ๊ฑฐ์ ๋๋ค. ์์ ์ธ์ด๋ก ์์ํ์ฌ ์์ ๊ณ ์ ๋ ํด๋ก์ ์์ฑ ์ธํธ๋ฅผ ํตํด ์ ๊ท ์ธ์ด๋ฅผ ์กฐํฉํ์ฌ ์ผ๋ฐ ์ธ์ด๋ฅผ ๊ตฌ์ฑ ํ ์ ์์ต๋๋ค. ํนํ ๋น ์ธ์ด, ๋น ๋ฌธ์์ด์ ํฌํจํ๋ ์ธ์ด ๋ฐ ๋ชจ๋ ๋จ์ผ ๋ฌธ์ ๋ฌธ์์ด์ ์ธ์ด๋ก ์์ํ๋ฉด ๊ณต์ฉ์ฒด, ์ฐ๊ฒฐ ๋ฐ Kleene ์คํ๋ฅผ ์ฌ์ฉํ์ฌ ๊ฐ๋ฅํ ๋ชจ๋ ์ ๊ท ์ธ์ด๋ฅผ ์ด์ ๋ธ ํ ์ ์์ต๋๋ค.
์ปจํ ์คํธ์๋ ์ธ์ด๋ฅผ ๋ชจ๋ ์์ฑํ๋ ๋ฐ ์ฌ์ฉํ ์์๋ ๊ธฐ๋ณธ ์ธ์ด ๋ฐ ํด๋ก์ ์์ฑ ์ธํธ๊ฐ ์์ต๋๊น? (๋ช ํํ๊ฒ : ๋๋ ๋น์ ์ด ๋ชจ๋ CFL์ ๋ํด ์ ๊ท ํํ์์ ์์ฑํ ์ ์๋์ง ๋ฌป์ง ์์ต๋๋ค. ๋ถ๊ฐ๋ฅํฉ๋๋ค. ๋์ , CFL์ ์ํด ์ ๊ท ํํ์๊ณผ ๊ฐ์ ํ๋ ์ ์ํฌ๋ฅผ ๋์์ธํ๋ ๋ฐฉ๋ฒ์ด ์๋์ง ๊ถ๊ธํฉ๋๋ค. ๋์ผํ ๊ธฐ๋ณธ ์์น.)