Theory of computation- Concept of string ,string length,empty string and epsilon<\/p>\n
[fvplayer id=”142″]<\/p>\n
In the Theory of Computation (TOC)<\/strong>, strings<\/strong> play a fundamental role in defining languages and automata. Let’s break down these concepts in a structured way:<\/p>\n A string<\/strong> is a finite sequence of symbols<\/strong> taken from a given alphabet (\u03a3)<\/strong>.<\/p>\n \u2714 If \u03a3 = {a, b}<\/strong>, then some possible strings are:<\/p>\n \u00a0A string must have a defined order of symbols<\/strong>. The length of a string<\/strong> is the number of symbols in it. It is denoted by |w|<\/strong>, where w<\/strong> is a string.<\/p>\n \u2714 Example:<\/strong><\/p>\n \u00a0The empty string (\u03b5)<\/strong> has a length of 0<\/strong>, i.e., |\u03b5| = 0<\/strong>.<\/p>\n \u00a0The empty string (\u03b5)<\/strong> is a valid string that contains no symbols<\/strong>. Epsilon (\u03b5) represents an empty string<\/strong>. \u00a0In Finite Automata (FA)<\/strong>, \u03b5 is used in \u03b5-transitions<\/strong> (NFA with \u03b5-moves), allowing transitions without consuming input symbols<\/strong>.<\/p>\n Concatenation (w\u2081 w\u2082):<\/strong> Joining two strings.<\/p>\n\u00a01. What is a String?<\/strong><\/h3>\n
\n
\"a\"<\/code>, \"b\"<\/code>, \"aa\"<\/code>, \"ab\"<\/code>, \"ba\"<\/code>, \"abb\"<\/code>, \"aabba\"<\/code>, etc.<\/li>\n<\/ul>\n
\u00a0It is case-sensitive<\/strong> (\"abc\"<\/code> \u2260 \"ABC\"<\/code>).<\/p>\n\u00a02. String Length ( |w| )<\/strong><\/h3>\n
\n
\u00a03. Empty String (\u03b5) vs. Null String<\/strong><\/h3>\n
\u00a0It is not the same as “null”<\/strong> or \" \"<\/code> (a space character).
Example:<\/strong> If \u03a3 = {a, b}, then \u03b5 is a string but does not contain ‘a’ or ‘b’<\/strong>.<\/p>\n\u00a04. Epsilon (\u03b5) in TOC<\/strong><\/h3>\n
It is important in formal languages, regular expressions, and automata<\/strong>.
\u00a0In a grammar (CFG, Regular Grammar, etc.)<\/strong>, \u03b5 can be used in productions<\/strong>:<\/p>\n\n
\u00a05. String Operations<\/strong><\/h3>\n
\n
\"abc\" + \"de\" = \"abcde\"<\/code>
Reversal (w\u02b3):<\/strong> Flipping the order of a string.<\/li>\n
Substring:<\/strong> A continuous part of a string.<\/li>\n\"ab\"<\/code> is a substring of \"abcde\"<\/code>.<\/li>\n<\/ul>\n\u00a0Summary<\/strong><\/h3>\n