Theory of ComputationTU Board 2078
Give the regular expressions for the following language over alphabet a, b. 1. Set of all strings with substring bab or abb. 1. Set of all strings whose 3^rd symbol is 'a' and 5^th symbol is 'b'.
10Give the regular expressions for the following language over alphabet {a, b}.
- Set of all strings with substring bab or abb.
- Set of all strings whose 3^rd symbol is 'a' and 5^th symbol is 'b'.
Answer
Alphabet Σ = {a, b}.
1. All strings containing the substring bab or abb
Any string, then one of the two substrings, then any string:
(a + b)* (bab + abb) (a + b)*
For example, aabba contains abb and bbabb contains bab, and both match.
2. All strings whose 3rd symbol is a and 5th symbol is b
Positions 1, 2 and 4 can be anything, position 3 must be a, position 5 must be b, and the rest can be anything:
(a + b)(a + b) a (a + b) b (a + b)*
For example, bbaab and abaabba match; aabab does not, because its 3rd symbol is b.
Discussion
Loading…
More Theory of Computation questions
Show that, For any NFA N=(Q, ∑, δ, q0, F) accepting language L=∑, There is a DFA D= (Q', ∑', q0′, δ', F') accepting the same language L.TU Board 207910State and prove the Pumping Lemma for regular languages. How can you show with example that pumping lemma is used to prove that a given language is not a…TU Board 207910Given the following expression grammar for simple arithematic expression with operator + and . E→ E+T T T → T+F F F → (E) a Remove the left recursion from…TU Board 207910Explain the ε closure of states on an ε NFA with suitable examples.TU Board 20795Convert the following regular expression into equivalent Finite Automata a) (0+1) 10(1+0) b) 1 0(0+1) 1TU Board 20795Define the term: Parse Tree, left most and right most derivation, sentential form and ambiguity with example.TU Board 20795