Trong lý thuyết ngôn ngữ hình thức, chuỗi trống (empty string) là chuỗi đặc biệt duy nhất có độ dài là 0.

Lý thuyết hình thứcSửa đổi

Xét về hình thức, chuỗi là một dãy ký tự (như chữ cái, chữ số hoặc khoảng trắng) có giới hạn, có thứ tự. Chuỗi trống là trường hợp đặc biệt khi dãy ký tự có độ dài bằng 0, như vậy, chuỗi trống không chứa bất kỳ ký tự nào. Bởi vì hai chuỗi được xác định là khác nhau nếu chúng có độ dài khác nhau hoặc có dãy ký tự khác nhau, nên chỉ tồn tại duy nhất một chuỗi trống. In formal treatments,[1] chuỗi trống được ký hiệu là ε hoặc đôi khi là Λ hoặc λ.

Không nên nhầm lẫn chuỗi trống với ngôn ngữ trống (empty language) ∅, là một ngôn ngữ hình thức (tập hợp các chuỗi) không chứa bất kỳ chuỗi nào, kể cả chuỗi trống.

Chuỗi trống có các tính chất sau:

  • |ε| = 0. Chiều dài chuỗi bằng 0.
  • ε ⋅ s = s ⋅ ε = s. Chuỗi trống là phần tử đơn vị của phép nối chuỗi. Tập hợp tất cả chuỗi tạo thành một monoid tự do đối với ⋅ và ε.
  • εR = ε. Nghịch đảo của chuỗi trống cũng là một chuỗi trống.
  • Chuỗi trống đứng trước mọi chuỗi còn lại theo thứ tự từ điển, bởi vì nó có độ dài ngắn nhất.[2]

Dùng trong ngôn ngữ lập trìnhSửa đổi

Trong hầu hết ngôn ngữ lập trình, chuỗi (string) là một kiểu dữ liệu. Về cơ bản, các chuỗi riêng rẽ được lưu vào các vị trí liên tiếp nhau trong bộ nhớ. Điều này có nghĩa là cùng một chuỗi (ví dụ, chuỗi trống) có thể được lưu ở hai vị trí khác nhau trong bộ nhớ. (Lưu ý rằng, thậm chí một chuỗi có độ dài là 0 cũng phải tốn dung lượng bộ nhớ để lưu nó, tùy thuộc vào định dạng sử dụng.) Như vậy, trong bộ nhớ có thể tồn tại nhiều chuỗi trống cùng một lúc, trái với định nghĩa theo lý thuyết hình thức, rằng chỉ tồn tại duy nhất một chuỗi trống. Tuy vậy, hàm so sánh chuỗi sẽ chỉ ra rằng tất cả các chuỗi trống này đều bằng nhau.

Trong hầu hết ngôn ngữ lập trình, chuỗi trống và tham chiếu rỗng (null reference hoặc null pointer, con trỏ rỗng) là hai khái niệm khác nhau bởi vì một tham chiếu rỗng/con trỏ rỗng không tham chiếu/trỏ tới bất kỳ chuỗi nào, kể cả chuỗi trống. Chuỗi trống là một chuỗi thật sự chính tắc, bởi hầu như tất cả hàm xử lý chuỗi đều có thể áp dụng với nó. Vài ngôn ngữ xử lý một số hoặc tất cả các khái niệm dưới đây cùng một cách, điều có thể làm giảm sự nguy hại trong cấu trúc điện toán: chuỗi trống, tham chiếu rỗng (null references), số nguyên 0, số thực dấu phẩy động 0, giá trị luận lý false, ký tự ASCII NUL, hoặc các giá trị tương tự khác.

Chuỗi trống được biểu diễn tương tự như các chuỗi khác. Khi ứng dụng trong cấu trúc điện toán có sử dụng ký tự kết chuỗi (string terminating character) (chuỗi kết thúc rỗng hoặc dòng văn bản thuần), chuỗi trống được biểu thị bằng việc sử dụng duy nhất ký tự kết chuỗi.

Biểu diễn λ Ngôn ngữ lập trình
"" C, C++, Java, C#, Perl, PHP, Python, JavaScript, Go, Visual Basic.NET, Haskell, Objective-C (dùng như chuỗi C), OCaml, Standard ML, Scala, Tcl, Lua
'' SQL, Perl, PHP, Python, JavaScript, Delphi, Pascal, Matlab
{'\0'} C, C++, Objective-C (dùng như chuỗi C)
std::string() C++
@"" Objective-C (dùng như một hằng đối tượng NSString)
[NSString string] Objective-C (dùng như một đối tượng NSString mới)
q(), qq() Perl
%{} Ruby
""""""
''''''
str()
Python
string.Empty C#, Visual Basic.NET
String.make 0 '-' OCaml
{} Tcl

Ví dụ chuỗi trốngSửa đổi

Chuỗi trống là cách biểu diễn hợp quy cách của zero trong phương pháp ký hiệu vị trí (ở mọi hệ cơ số), mà không chứa số 0 đứng đầu (leading zero). Do chuỗi trống không có kiểu biểu diễn tiêu chuẩn nào khác ngoài định nghĩa trong lý thuyết ngôn ngữ hình thức, số không với kiểu biểu diễn truyền thống ở dạng một chữ số thập phân 0 được dùng thay thế.

Vùng nhớ Zero-filled, được biên dịch thành chuỗi kết thúc rỗng, là một chuỗi trống.

Dòng văn bản trống thể hiện một chuỗi trống. Hiện tượng này xảy ra khi có hai EOL liên tiếp, như thường xảy ra trong tập tin văn bản, và đôi khi được sử dụng trong quá trình xử lý văn bản để chia tách các đoạn văn, ví dụ như ở MediaWiki.

Xem thêmSửa đổi

Tham khảoSửa đổi

  1. ^ JOHN CORCORAN, WILLIAM FRANK, and MICHAEL MALONEY, String theory, Journal of Symbolic Logic, vol. 39 (1974) pp. 625– 637
  2. ^ CSE1002 Lecture Notes - Lexicographic