Радковы тып

У праграмаванні, тэкставы радок, або радок (англ. string) — гэта паслядоўнасць знакаў альбо ў форме літарала, альбо ў форме пераменнай. У апошнім выпадку элементы і/альбо даўжыня радка могуць змяняцца, але могуць быць і фіксаванымі (пасля стварэння). Тэкставы радок у асноўным разглядаюць як тып даных, які часта рэалізаваны як масіў байтаў (альбо слоў), і захоўвае паслядоўнасць элементаў, звычайна — знакаў, у нейкай кадзіроўцы. Радок можа азначаць і больш агульныя масівы альбо паслядоўнасці (спісы) і структуры.

У залежнасці ад мовы праграмавання і выбранага тыпу даных, пераменная, аб'яўленая як радок, можа альбо займаць загадзя вызначаны аб'ём памяці пад сваю максімальную даўжыню, альбо займаць памяць дынамічна, тым самым падстройваючыся пад колькасць элементаў.

Калі радок (разам са сваім змесцівам) вызначаны ў непасрэдна зыходным кодзе, яго называюць радковым літаралам.

У фармальных мовах, што ўжываюцца ў матэматычнай логіцы і тэарэтычнай інфарматыцы, радок — гэта канечная паслядоўнасць знакаў, што належаць мноству, якое называецца алфавітам.

Фармальная тэорыя

Няхай Σ будзе непустым канечным мноствам літар алфавіта. Элементы Σ называюцца сімваламі альбо знакамі. Радок (альбо слова) над Σ — гэта любая канечная паслядоўнасць знакаў з Σ. Напрыклад, калі Σ = {0, 1}, то 01011 будзе радком над Σ.

Даўжыня радка — гэта колькасць знакаў у радку, альбо даўжыня паслядоўнасці, якая можа прымаць любыя неадмоўныя значэнні. Пусты радок — гэта радок над Σ з нулявой даўжынёй. Абазначаецца як ε альбо λ.

Мноства ўсіх радкоў над Σ з даўжынёй n абазначаецца Σⁿ. Напрыклад, калі Σ = {0, 1}, то Σ² = {00, 01, 10, 11}. Варта заўважыць, што Σ⁰ = {ε} для любога алфавіта Σ.

Мноства ўсіх радкоў над Σ з любой даўжынёй — гэта замыканнем Кліні алфавіта Σ і абазначаецца як Σ*. У тэрмінах Σⁿ,

$\Sigma ^{*}=\bigcup _{n\in \mathbb {N} }\Sigma ^{n}$

Напрыклад, калі Σ = {0, 1}, Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …}, дзе Σ* — злічальнае мноства, а ўсе элементы Σ* маюць канечную даўжыню.

Мноства радкоў над Σ (г.зн. любое падмноства мноства Σ*) называецца фармальнай мовай над Σ. Напрыклад, калі Σ = {0, 1}, то мноства радкоў з цотнай колькасцю нулёў ({ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, …}) з'яўляецца фармальнай мовай над Σ.

Канкатэнацыя і падрадкі

Канкатэнацыя — гэта важная бінарная аперацыя на мностве Σ*. Для любых двух радкоў s і t з мноства Σ* канкатэнацыя вызначаецца як паслядоўнасць знакаў радка s, за якімі ідзе паслядоўнасць знакаў радка t, і абазначаецца st. Напрыклад, калі Σ = {a, b, …, z}, s = bear, а t = hug, то st = bearhug, а ts = hugbear.

Канкатэнацыя радкоў — аперацыя асацыятыўная, але некамутатыўная. Пусты радок выступае як нейтральны элемент; для любога радка s, εs = sε = s. Такім чынам, мноства Σ* і аперацыя канкатэнацыя ўтвараюць маноід.