Write a regular expression for the language of all strings over {a,b} in which every b...

Write a regular expression for the language of all strings over {a,b} in which every b is directly preceded by a, and may not be directly followed by more than two consecutive a symbols.

Expert Solution

sol: In these type of questions try to construct the strings of different lengths according to the given conditions.

Here,the conditions are:

i)Every b must be directly preceded by a that means no b can come before a always.

ii)Each b must not be directly followed by not more than 2 a's.Therefore after b either one a or two a can occur only.

1)Now construct strings of different lengths keeping in mind of these above conditions:-

Strings of 0 length - epsilon(empty string)

String of length 1- a

Strings of length 2- aa,ab

Strings of length 3-aab,aba

Strings of length 4- aaba,abab,abaa

.... and so on

2)Now construct dfa which can satisfies the above string pattern and find the regular expression using it:

venereology answered 1 year ago

Write regular expressions that describes the following language: The language over {0,1,/} that contains all and...

Write regular expressions that describes the following language: The language over {0,1,/} that contains all and only the strings that are base-2 (as above, you can use base-10 if you prefer) representations of rational numbers. Define a representation of a rational number to be either a representation of an integer, or two representations of integers separated by “/”. Leading 0s are allowed this time.

Write regular expressions that describes the following language: The language over {0,1} that contains all and...

Write regular expressions that describes the following language: The language over {0,1} that contains all and only the strings that are base-2 representations of odd positive integers. Do not allow leading 0s. (If you are more comfortable writing bulky regular expressions than you are working in base-2, you may write a regular expression for strings that are base-10 representations of odd integers without leading 0s, using alphabet {0,1,2,3,4,5,6,7,8,9}.)

S is the language over S = {a, b, c, d, e} containing all strings that...

S is the language over S = {a, b, c, d, e} containing all strings that start with at least 2 a's, followed by any number of b's, followed by 5 c's, followed by an odd number of d's, followed by an even number of e's. For example, S contains aaabbcccccdee, aaaacccccdddeeee, and so on. Write S symbolically in the manner of section 6.1, problem # 12 a) - f). Example 6.12 will also be helpful. bonus: How many strings in {000, 11}*...

1. Provide a regular expression that describes all bit-strings that length is at least one and...

1. Provide a regular expression that describes all bit-strings that length is at least one and at most three. 2. Provide a regular expression that describes all bit strings with odd length.

4. Construct regular expressions for the following languages over the alphabet {a, b}: a. Strings that...

4. 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. 5. Let ? = {? ?? ?? ? | ? > ? + ?}. a. List all strings of length 7. (use power notation: i.e. aabbbbaaaaaaaa is a2b 4a 8 ) b. Use the Pumping Lemma for Regular Languages to prove that L is not regular.

Prove the language of strings over {a, b} of the form (b^m)(a^n) , 0 ≤ m...

Prove the language of strings over {a, b} of the form (b^m)(a^n) , 0 ≤ m < n-2 isn’t regular. (I'm using the ^ notation but your free to make yours bman instead of (b^m)(a^n) ) Use the pumping lemma for regular languages.

Consider the language L over alphabets (a, b) that produces strings of the form aa* (a...

Consider the language L over alphabets (a, b) that produces strings of the form aa* (a + b) b*a. a) Construct a nondeterministic finite automata (NFA) for the language L given above. b) Construct a deterministic finite automaton (DFA) for the NFA you have constructed above.

1. What is a regular expression? Write a regular expression that will detect “College” and “collegE”....

1. What is a regular expression? Write a regular expression that will detect “College” and “collegE”. 2. What is degree centrality? Create a graph of 4 vertices and compute the degree centrality of the vertices. 3. Compute internal and external community densities for a graph containing 6 nodes. You can create any graph of 6 nodes with at least 4 edges.

Construct a PDA that matches all strings in the language over {x,y} such that each string...

Construct a PDA that matches all strings in the language over {x,y} such that each string has at least twice as many y's as x's. Below, give a short description of the set of strings associated with each state of your PDA.

1. Prove the language L is not regular, over the alphabet Σ = {a, b}. L...

1. Prove the language L is not regular, over the alphabet Σ = {a, b}. L = { aib2i : i > 0} 2) Prove the language M is not regular, over the alphabet Σ = {a, b}. M = { wwR : w is an element of Σ* i.e. w is any string, and wR means the string w written in reverse}. In other words, language M is even-length palindromes.

Question