Give regular expressions describing each of the following regular languages over Σ = {0,1}:
{w : w begins and ends with the same
symbols}
show work!
Answer: -------- (0(0+1)*0) + (1(0+1)*1) Explanation: -------------- (0+1) matches exactly one 0 or 1 and, (0+1)* matches 0 or more 0's and 1's together so, 0(0+1)*0 indicates binary strings beginning and ending with 0 and, 1(0+1)*1 indicates binary strings beginning and ending with 1 finally, (0(0+1)*0) + (1(0+1)*1) matches all binary strings which start and end with same symbol.
Give regular expressions describing each of the following regular languages over Σ = {0,1}: {w :...
Give regular expressions describing each of the following regular languages over Σ = {0,1}: {w : |w| = 3} (PLEASE SHOW WORK)
Provide regular expressions for the following languages: a.) The set of strings over {0,1} whose tenth symbol from the right end is 1. b) The set of strings over {0,1} not containing 101 as a sub-string. ***IMPORTANT: PLEASE SHOW ALL WORK AND ALL STEPS, NOT JUST THE ANSWERS!!!
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...
1. Give a DFA for each of the following languages defined over the alphabet Σ (0, i): a) (3 points) L={ w | w contains the substring 101 } b) (3 points) L-wl w ends in 001)
1(a)Draw the state diagram for a DFA for accepting the following language over alphabet {0,1}: {w | the length of w is at least 2 and has the same symbol in its 2nd and last positions} (b)Draw the state diagram for an NFA for accepting the following language over alphabet {0,1} (Use as few states as possible): {w | w is of the form 1*(01 ∪ 10*)*} (c)If A is a language with alphabet Σ, the complement of A is...
4) (9 pts) Give regular expressions for the following languages on (la, b) a) L1 = { w : na(w) mod 3 = 1). b) L2w w ends in aa) c) L3 = all strings containing no more than three a's.
Classify the following languages over {0,1} as finite, regular, cf and beyond cf. Give the smallest family possible! • At most five occurences of 1 [ ] finite [ ] regular [ ] cf [ ] beyond • Length < 20 [ ] finite [ ] regular [ ] cf [ ] beyond • Length > 20 [ ] finite [ ] regular [ ] cf [ ] beyond
Give context-free grammars generating each of the following languages over Σ = {0, 1}: {w : |w| ≤ 5} {w : |w| > 5 or its third symbol is 1} {w : every odd position of w is 1}
give the regular expressions for each of the following languages u.{xy {a, b}* | the number of as in x is odd and the number of bs in y is even}
Give a regular expression generating the following languages over the alphabet {a,b}: {w | w is any string except aa and bbb}