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.

Solutions

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 3 months ago

Next > < Previous

Related Solutions

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.

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.

Determine if the language ?={?^?∶?=?^3????????≥0}over Σ={?}is regular.

Pattern matching using python3 re module Write a regular expression that will find out all the...

Pattern matching using python3 re module Write a regular expression that will find out all the words that ends with 4 consecutive vowels at the end. Example: import re f=open("/usr/share/dict/american-english",'r') pattern='a[a-z]*d$' words=f.readlines() matchlist=[word for word in words if re.match(pattern,word)] =============================== Generate random string follow a specific pattern You will take a username and ask user for the password. User has to enter a strong password in order to create his or her account. The criteria for strong password is, a)...

Which one of the following REs represents the language of all binary strings having two consecutive...

Which one of the following REs represents the language of all binary strings having two consecutive 0s and two consecutive 1s? a. (0 + 1)*00(0 + 1)* + (0 + 1)*11(0 + 1)* b. (0 + 1)*0011(0 + 1)* + (0 + 1)*1100(0 + 1)* c.(0 + 1)*(00(0 + 1)*11 + 11(0 + 1)*00)(0 + 1)* d. 00(0 + 1)*11 + 11(0 + 1)*00

Regular Expressions Assignment Write a regular expression for each of the following. Can you show output...

Regular Expressions Assignment Write a regular expression for each of the following. Can you show output please. A blank line (may contain spaces) Postal abbreviation (2 letters) for State followed by a space and then the 5-digit zip code A KU student username (Ex. lpork247) A “valid” email address (also explain how you defined “valid”) A SSN pattern (ddd-dd-dddd)

Draw PDA transition diagram for the following language: The set of strings over the alphabet {x,...

Draw PDA transition diagram for the following language: The set of strings over the alphabet {x, y} where 2 * (# of x's) = 3 * (#y's) That is, if we let nx be the number of x's and ny be the number of y's, then the strings in these language are those where 2nx = 3ny Try to find a PDA that is as simple and elegant as possible (do not convert from CFG). ------------------------------------------------------------------------------------------------------------------ USE Notation between transition:...

Subjects