Let L = {x = a^rb^s | r + s = 1mod2}, I.e, r + s...

Let L = {x = a^rb^s | r + s = 1mod2}, I.e, r + s is an odd number. Is L regular or not? Give a proof that your answer is correct.

Solutions

Expert Solution

Answer : the language L is NOT regular.

=> Some Points for regular and not regular :

1. Every finite set represents a regular language.

2. Given an expression of non-regular language, but the value of parameter is bounded by some constant, then the language is regular (means it has kind of finite comparison).

3. The pattern of strings form an A.P.(Arithmetic Progression) is regular(i.e it’s power is in form of linear expression),
but the pattern with G.P.(Geometric Progression) is not regular(i.e its power is in form of non-linear expression) and it comes under class of Context Sensitive Language.

4. No pattern is present, that could be repeated to generate all the strings in language is not regular.Finding prime itself is not possible with FA.

5. A concatenation of pattern(regular) and a non-pattern(not regular) is also not a regular language.

6. Whenever unbounded storage is required for storing the count and then comparison with other unbounded counts, then the language is not regular.

Reason for NOT regular language of L is :

=> the language is infinite (not finite).

=> There is no any pattern in strings of language.

venereology answered 10 months ago

Next > < Previous

Related Solutions

Let L = {x = a r b s c t | r + s =...

Let L = {x = a r b s c t | r + s = t, r, s, t ≥ 0}. Give the simplest proof you can that L is not regular using the pumping lemma.

Let L = {0 r | r = s 2 , s a positive integer}. Give...

Let L = {0 r | r = s 2 , s a positive integer}. Give the simplest proof you can that L is not regular using the pumping lemma.

Let A = R x R, and let a relation S be defined as: “(x1, y1)...

Let A = R x R, and let a relation S be defined as: “(x1, y1) S (x2, y2) ⬄ points (x1, y1) and (x2, y2)are 5 units apart.” Determine whether S is reflexive, symmetric, or transitive. If the answer is “yes,” give a justification (full proof is not needed); if the answer is “no” you must give a counterexample.

L = {a r b s | r, s ≥ 0 and s = r 2}....

L = {a r b s | r, s ≥ 0 and s = r 2}. Show that L is not regular using the pumping lemma

Let R and S be nontrivial rings (i.e., containing more than just the 0 element), and...

Let R and S be nontrivial rings (i.e., containing more than just the 0 element), and define the projection homomorphism pi_1: R X S --> R by pi_1(x,y)=x. (a) Prove that pi_1 is a surjective homomorphism of rings. (b) Prove that pi_1 is not injective (c) Prove that (R X S)/R (not congruent) R. Please show all parts of answer

Let R and S be equivalence relations on a set X. Which of the following are...

Let R and S be equivalence relations on a set X. Which of the following are necessarily equivalence relations? (1)R ∩ S (2)R \ S . Please show me the proof. Thanks!

Let x be a set and let R be a relation on x such x is...

Let x be a set and let R be a relation on x such x is simultaneously reflexive, symmetric, and antisymmetric. Prove equivalence relation.

Let P(x),Q(x),R(x), and S(x) be the statements “x is a duck,” “x is one of my...

Let P(x),Q(x),R(x), and S(x) be the statements “x is a duck,” “x is one of my poultry,” “x is an oﬃcer,” and “x is willing to waltz,” respectively. Express each of these statements using quantiﬁers, logical connectives, and the relations P(x),Q(x),R(x), and S(x). (a) No ducks are willing to waltz (b) No oﬃcers ever decline to waltz (c) All my poultry are ducks (d) My poultry are not oﬃcers (e) Does the fourth item follow from the ﬁrst three taken...

Let S ⊆ R and let G be an arbitrary isometry of R . Prove that...

Let S ⊆ R and let G be an arbitrary isometry of R . Prove that the symmetry group of G(S) is isomorphic to the symmetry group of S. Hint: If F is a symmetry of S, what is the corresponding symmetry of G(S)?

Let L ⊆ Σ ∗ and define S(L), the suffix-language of L, as S(L) = {w...

Let L ⊆ Σ ∗ and define S(L), the suffix-language of L, as S(L) = {w ∈ Σ ∗ | x = yw for some x ∈ L, y ∈ Σ ∗ } Show that if L is regular, then S(L) is also regular.

Subjects