Give a regular expression generating the following languages over the alphabet {a,b}:
{w | w is any string except aa and bbb}
--> Since we need to remove two strings specifically, First simply add all the strings
till length 3 except those not needed.
ε + (a+b) + (ab+ba+ab) + (aaa+aab+aba+abb+bab+bba+bba)
--> Notice that 'aa' and 'bbb' are not there.
--> Now add expression for all strings of length 4 and above.
(a+b)(a+b)(a+b)(a+b)(a+b)*
--> Join both these expressions.
ε + (a+b) + (ab+ba+ab) + (aaa+aab+aba+abb+bab+bba+bba) +
(a+b)(a+b)(a+b)(a+b)(a+b)*
--> We can further simply it by taking some terms common, But this from is also ok.
To generate the language {w | w is any string except "aa" and "bbb"} over the alphabet {a, b}, we can use a regular expression that covers all possible strings while excluding the specific patterns "aa" and "bbb". Here's the regular expression:
^(?!(aa|bbb))[ab]*$
Explanation:
^: Denotes the start of the string.
(?!(aa|bbb)): A negative lookahead assertion. This ensures that the string does not start with "aa" or "bbb". If it does, the match fails.
[ab]*: Matches any combination of "a" and "b", including empty string (i.e., zero occurrences of "a" and "b").
$: Denotes the end of the string.
The regular expression will generate all possible strings over {a, b} except for "aa" and "bbb". For example, it will match strings like "a", "b", "aba", "babab", "baaab", "aabab", etc., but it will not match "aa" or "bbb".
Give a regular expression generating the following languages over the alphabet {a,b}: {w | w is...
Give regular expressions generating the languages of 1. {w over the alphabet of {0, 1} | w is any string except 11 and 111} 2. {w over the alphabet of {0, 1} | w contains at least two 0’s and at most one 1} 3. {w over the alphabet of {0, 1} | the length of w is at most 9} 4. {w over the alphabet of {0, 1} | w contains at least three 1 s} 5. {w over...
Give a regular expression for these languages i) {w| w is a word of the alphabet = {0,1} that represents an integer in a binary form that is a multiple of 4} ii) {w belongs to {0,1,2}* | w contains the string ab exactly 2 times but not at the end} iii) { w belongs to {0,1,2}* | w=uxvx that x belongs to {0,1,2} u,v belongs to {0,1,2}* and there isn't any string y in the sequence v that x<y}
Construct DFA's that recognize the following languages over the alphabet {a,b}: 1. {w|w is any string except abba or aba}. Prove that your DFA recognizes exactly the specified language. 2. {w|w contains a substring either ababb or bbb}. Write the formal description for this DFA too.
Give the regular expressions of the following languages (alphabet is ab): a. {w | w has a length of at least three and its second symbol is a b} b. {w | w begins with an a and ends with a b} c. {w | w contains a single b} d. {w | w contains at least three a's} e. {w | w contains the substring baba} d. {w | w is a string of even length} e. The empty...
3) Construct a regular expression defining each of the following languages over the alphabet {a, b}. (a) L = {aab, ba, bb, baab}; (b) The language of all strings containing exactly two b's. (c) The language of all strings containing at least one a and at least one b. (d) The language of all strings that do not end with ba. (e) The language of all strings that do not containing the substring bb. (f) The language of all strings...
Construct regular expressions for the following languages over the alphabet {a, b}: a. Strings that do not begin with an “a”. b. Strings that contain both aa and bb as substrings.
1. (a) Give state diagrams of DFA’s recognizing the following languages. That alphabet is Σ = {a,b} L1 = {w | w any string that does not contain the substring aab} L2 = {w | w ∈ A where A = Σ*− {a, aa, b}} 2. (a) Give state diagrams of DFA’s recognizing the following languages. The alphabet is {0, 1}. L3 = {w | w begins with 0 ends with 1} (b) Write the formal definition of the DFA...
4. A regular expression for the language over the alphabet fa, b) with each string having an even number of a's is (b*ab*ab*)*b*. Use this result to find regular expressions for the following languages a language over the same alphabet but with each string having odd number of a's. (3 points) a. b. a language over the same alphabet but with each string having 4n (n >- 0) a's. (3 points)
8 Find CFGs that for these regular languages over the alphabet a, b. Draw a Finite Automata first and use this to create the CFG (a) The language of all words that consist only of double letters (aa or bb) (b) The set of all words that begin with the letter b and contains an odd number of a's or begin with the letter a and contains an even number of b's.
The pumping lemma for regular languages is Theorem 1.70 on page 78 of the required text. Definition: w is a string if and only if there exists an alphabet such that w is a string over that alphabet. Note: For every alphabet, the empty string is a string over that alphabet. Notation: For any symbol o, gº denotes the empty string, and for every positive integer k, ok denotes the string of length k over the alphabet {o}. 1) (20%]...