Đề thi môn ngôn ngữ hình thức và otomat

Giả sử L là ngôn ngữ chính quy. Khi đó sẽ tồn tại một DFA M chấp nhận cho ngôn ngữ L. Gọi n là số trạng thái của DFA M đó. Xét chuỗi z = anb1c1dn . Ta có độ dài của chuỗi z là: |z| = 2n + 2 n . Theo bổ đề bơm, ta có thể đặt z = uvw , trong đó u, v, w là các chuỗi con của z với điều kiện như sau: |uv| ≤ n, |v| ≥ 1 và với mọi i ≥ 0 ta có uviw ϵ L