If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?

L . L^R = {xy | x ϵ L, y^R ϵ L}
{ww^R| w ϵ L}
Prefix (L) = {x ϵ ∑^* | ∃x ϵ ∑^*such that xy ϵ L}
Suffix (L) = {y ϵ ∑^* | ∃x ϵ ∑^*such that xy ϵ L}

LohaHridoy

4 views

2025-01-04 04:42

1 Answers

AhmedNazir

Option 2 : {wwR | w ϵ L}

Non-deterministic push down automata (NPDA) determines the middle position of the string in the language and start popping until Z(end of stack elements) is meet to tell the acceptance of it .
As all the string present in the language ww^Raccepted by NPDA Hence it is a context free language (CFL).
From the properties of regular language: Reverse, Suffix, Prefix, Concatenation of Regular language is Regular.
Every regular language is context free language, but every context free language is not a regular language also ww^R it is not possible to give, DFA, NFA or ϵ - NFA accepting the language. Therefore, it is not Regular language.

4 views Answered 2022-09-04 04:29

Related Questions

Language L1 is defined by the grammar: S1 → aS1b|ϵ Language L2 is defined by the grammar: S2 → abS2|ϵ Consider the following statements: P: L1 is regular Q: L2 is regular Which one of the following is TRUE?

1 Answers 4 Views

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y̅ reduces to W, and Z reduces to X̅ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

1 Answers 4 Views

Consider the following languages L1 = {ap | p is a prime number} L2 = {anbmc2m | n ≥ 0, m ≥ 0} L3 = {anbnc2n | n ≥ 0} L4 = {anbn | n ≥ 1} Which of the following are CORRECT I. L1 is context-free but not regular. II. L2 is not context-free III. L3 is not context-free but recursive. IV. L4 is deterministic context-free?

1 Answers 5 Views

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable I. Given a regular expression R and a string w, is w ∈ L(R) II. Given a context-free grammar G, is L(G) = ϕ III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑ IV. Given a Turing machine M and a string w, is w ∈ L(M) ?

1 Answers 4 Views

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT I. L1 ∪ L2 is context-free II. L̅1 is context-free III. L1 – R is context-free IV. L1 ∩ L2 is context-free?

1 Answers 5 Views

Consider the following languages over the alphabet ∑ = {a, b, c} Let L1 = {an bn cm | m, n ≥ 0} and L2 = {am bn cn | m, n ≥ 0} Which of the following are context-free languages I. L1 ∪ L2 II. L1 ∩ L2?

1 Answers 7 Views

Consider the following sets: S1. Set of all recursively enumerable languages over the alphabet {0,1} S2. Set of all syntactically valid C programs S3. Set of all languages over the alphabet {0,1} S4. Set of all non-regular languages over the alphabet {0,1} Which of the above sets are uncountable?

1 Answers 6 Views

A library contained books in Hindi, English and several regional languages, such that the average number of books per language are 525, while the average number of books per regional language are 225. If the total number of Hindi and English books in the library is 2100 more than the total number of books in the regional languages, find the number of regional languages in which books are kept in the library.?

1 Answers 5 Views

The points in the graph below represent the halts of a lift for durations of 1 minute, over a period of 1 hour. Which of the following statements are correct i. The elevator never moves directly from any non-ground floor to another non-ground floor over the one hour period ii. The elevator stays on the fourth floor for the longest duration over the one hour period?

1 Answers 6 Views

Consider the following statements: (1) If n ≥ 3 and m ≥ 3 are distinct positive integers, then the sum of exterior angles of a regular polygon of m sides is different from the sum of exterior angles of regular polygon of n sides (2) Let m, n be integers such that m > n ≥ 3. Then the sum of the interior angles of regular polygon of sides is greater than the sum of interior angles of a regular polygon of n sides, and their sum is (m + n)π/2 Which of the above statements is/are correct?

1 Answers 6 Views

এক্সাম দিয়ে মেধা যাচাই করুন

Job Preparation (1125)

Admission (754)

এসএসসি (10)

এইচএসসি (5)