SKILLWILL

Regular Language Questions

1. Which of the following grammar is Type 2 grammar according to Chomsky classification of grammar?
(a) aSaS->a,S->b (b) SA ->aA | bBBc| a (c) aAS->abA, A->λ (d) None of these

Explanation:

According to the Chomsky hierarchy, Type 2 grammar refers to context-free grammars (CFG), where each production rule has the form:

A

Here, $A$ is a single non-terminal symbol, and $\alpha$ is a string consisting of terminals and/or non-terminals. The key property is that the left-hand side of the production rule must be a single non-terminal.
========================================================================

2. Consider the following grammar G with productions,

S ->aAbB, aA->bBA| bB, B ->b | λ, then G is (a) Regular grammar (b) Context free grammar (c) Context Sensitive grammar (d) Unrestricted grammar

Explanation:

Context-Free Grammar (CFG):

A grammar is context-free if all production rules are of the form $A \rightarrow \alpha$ , where $A$ is a single non-terminal symbol, and $\alpha$ is a string of terminals and/or non-terminals.

In this grammar, each left-hand side of the production rules starts with a non-terminal, and the right-hand side is a string of terminals and/or non-terminals.
The rule B → λ is valid for CFGs as context-free grammars allow null (ε) productions.

Thus, the grammar fits the definition of a context-free grammar.
========================================================================

3. How many of the following rules would not be permitted in a context-sensitive grammar?__

1. aA → bbA 2.bA → aB 3.ABb → C 4.ab → B 5. cAAb → aaaa 6. A ->λ

Explanation:

In a context-sensitive grammar, all production rules must satisfy the condition that the length of the string on the left-hand side is less than or equal to the length of the string on the right-hand side, i.e., no shrinking of strings is allowed. Additionally, context-sensitive grammars do not allow the production of the empty string (λ) unless the grammar only produces λ.

Rules analysis:

aA → bbA
- Left-hand side: "aA" (length = 2)
- Right-hand side: "bbA" (length = 3)
- This rule is permitted because the length on the right is greater than the left.
bA → aB
- Left-hand side: "bA" (length = 2)
- Right-hand side: "aB" (length = 2)
- This rule is permitted because the length on both sides is equal.
ABb → C
- Left-hand side: "ABb" (length = 3)
- Right-hand side: "C" (length = 1)
- This rule is not permitted because the right-hand side is shorter than the left (shrinking).
ab → B
- Left-hand side: "ab" (length = 2)
- Right-hand side: "B" (length = 1)
- This rule is not permitted because the right-hand side is shorter than the left (shrinking).
cAAb → aaaa
- Left-hand side: "cAAb" (length = 4)
- Right-hand side: "aaaa" (length = 4)
- This rule is permitted because the lengths are equal.
A → λ

This rule is not permitted in a context-sensitive grammar, as λ productions (producing the empty string) are not allowed unless the grammar only generates λ.

========================================================================

4. Consider the following grammar G
S-> RST|abc| d, T->cdB | Rab, R->abcR | ab Then G is which type of Chomsky classification of grammar? (a) Type 0 (b) Type 1 (c) Type 2 (d) Type 3

Explanation:

Context-Free Grammar (CFG) - Type 2:

A grammar is context-free if all production rules are of the form:

A \rightarrow \alpha

where $A$ is a single non-terminal, and $\alpha$ is a string of terminals and/or non-terminals.

In this grammar:

Each rule has a single non-terminal on the left-hand side (e.g., $S$ , $T$ , or $R$ ).
The right-hand sides of the production rules are strings consisting of terminals and non-terminals.

Since all the rules conform to the form $A \rightarrow \alpha$ , this grammar satisfies the conditions of a context-free grammar (Type 2).
=========================================================================

5. Which of the following languages cannot be accepted by an NFA? (i) {akn | n, k ≥ 0 and n is multiple of k} (ii) {(ab)n | n ≥ 0}.{an | n ≥ 0} (iii) {anbbam | n, m ≥ 0} (iv) {anbban | n ≥ 0} (a) i, iv only (b) ii, iii only (c) i, ii, iv only (d) iii only

Explanation:

(i) ${a^{k} n ∣ n, k \geq 0 and n is a multiple of k}$

This language describes strings where $n$ is a multiple of $k$ . For instance, for every $k$ , $n$ must satisfy $n = m \times k$ for some integer $m$ .
This is a complex relationship between $n$ and $k$ that requires counting and comparing values of $n$ and $k$ , which cannot be done by a finite automaton (neither DFA nor NFA) since finite automata cannot perform arithmetic comparisons or count dependencies like "multiples" between two variables.
Conclusion: This language cannot be accepted by an NFA.

(ii) ${(a b)^{n} ∣ n \geq 0} \cdot {a^{n} ∣ n \geq 0}$

This language consists of two parts: the first part has alternating "ab" pairs repeated $n$ times, followed by $n$ "a"s.
This requires the automaton to count how many "ab" pairs have been seen and ensure that the number of "a"s in the second part matches that count. NFAs (and DFAs) cannot count and store the value of $n$ without unbounded memory, making it impossible for an NFA to recognize this pattern.
Conclusion: This language cannot be accepted by an NFA.

(iii) ${a^{n} b b a^{m} ∣ n, m \geq 0}$

This language consists of any number of "a"s followed by two "b"s and then any number of "a"s. NFAs can easily handle patterns where the number of symbols before and after a middle segment (like the "bb") can vary independently.
Conclusion: This language can be accepted by an NFA.

(iv) ${a^{n} b b a^{n} ∣ n \geq 0}$

This language requires the number of "a"s before and after the "bb" to be exactly equal. This is a classic example of a language that requires counting and comparison between two segments (the "a"s before and after the "bb"). Finite automata (including NFAs) cannot count or remember how many "a"s have been seen in one part to compare with the number of "a"s in another part.
Conclusion: This language cannot be accepted by an NFA.
====================================================================

6. Which of the following statement is/are true?

1. If complement of L is non-regular then L is also non-regular. 2. If L* is regular then L must be regular. 3. If L1  L2 is regular then at least one of them (i.e. L1 or L2) must be regular. 4. If L1 is regular and L2 is non-regular language then L1 – L2 is not regular. (a) 1 only (b) 1, 2 & 3 only (c) 1 & 3 only (d) 2 & 4 only

Statement 1:

If the complement of $L$ is non-regular, then $L$ is also non-regular.

This statement is true. By the closure properties of regular languages, if $L$ is regular, then its complement $\overline{L}$ is also regular. Therefore, if $\overline{L}$ is non-regular, $L$ must also be non-regular.

Statement 2:

If $L^*$ is regular, then $L$ must be regular.

This statement is false. For example, consider $L = \{ a^n b^n | n \geq 0 \}$ , which is a non-regular language. However, $L^*$ would include strings like $a^m b^m$ for various $m$ , and the concatenation of such strings does not impose the $a^n b^n$ constraint. In fact, $L^*$ can generate any string composed of 'a's and 'b's, making it regular.

Statement 3:

If $L_1 \cup L_2$ is regular, then at least one of them (i.e., $L_1$ or $L_2$ ) must be regular.

This statement is false. For example, let $L_1 = \{ a^n b^n | n \geq 0 \}$ and $L_2 = \{ b^n a^n | n \geq 0 \}$ . Both $L_1$ and $L_2$ are non-regular languages, but $L_1 \cup L_2$ can result in a regular language such as $\{ a, b \}^*$ .

Statement 4:

If $L_1$ is regular and $L_2$ is a non-regular language, then $L_1 - L_2$ is not regular.

This statement is false. The difference between a regular and a non-regular language can still be regular. For instance, if $L_1 = \{ a, b \}^*$ (which is regular) and $L_2$ is a non-regular language, $L_1 - L_2$ can still be regular, depending on the construction of $L_2$ .

Conclusion:

True Statements: 1
False Statements: 2, 3, 4

Final Answer:

The correct option is (a) 1 only
======================================================================

7. Which of the following grammar is regular and generates regular language?
1. S → Saaa | aS | a 2. S → aaS | bS | λ 3. S → aS | bbS | λ 4. S → aS | bSb | λ (a) 1, 2, 3 & 4 (b) 1, 2 & 4 only (c) 2, 3 only (d) 3 only

1. $S \to S aaa ∣ a S ∣ a$

The production $S \rightarrow Saaa$ introduces three 'a's on the right side, which means this production is not linear (it adds multiple symbols simultaneously).
The second production $S \rightarrow aS$ is right-linear (it has a terminal followed by a non-terminal).
The third production $S \rightarrow a$ is a valid regular grammar production because it replaces the non-terminal $S$ with a terminal $a$ .

Since $S \rightarrow Saaa$ is not a valid regular production, this grammar is not regular and does not generate a regular language.

2. $S → aa S ∣ b S ∣ λ$

$S \rightarrow aaS$ is not regular because it introduces two 'a's at once, violating the right-linear condition.
$S \rightarrow bS$ is a valid right-linear production.
$S \rightarrow \lambda$ is allowed for regular languages (it represents the empty string).

Since the rule $S \rightarrow aaS$ is not regular, this grammar is not regular and does not generate a regular language.

3. $S \rightarrow aS \ | \ bbS \ | \ \lambda$

$S \rightarrow aS$ is a valid right-linear production.
$S \rightarrow bbS$ introduces two 'b's at once, which again violates the right-linear condition.
$S \rightarrow \lambda$ is allowed in regular grammars.

Since $S \rightarrow bbS$ is not a valid regular production, this grammar is not regular and does not generate a regular language.

4. $S → a S ∣ b S b ∣ λ$

$S \rightarrow aS$ is a valid right-linear production.
$S \rightarrow bSb$ introduces a non-terminal in the middle of the string, which means it's a context-free grammar, not a regular grammar.
$S \rightarrow \lambda$ is valid for regular grammars.

Since $S \rightarrow bSb$ is not regular (it is a context-free rule), this grammar is not regular and does not generate a regular language.

Conclusion:

None of the given grammars are regular, and none generate regular languages.

Thus, none of the grammars are regular, and the correct answer is (d) 3 only because it comes closest to being regular, although it's not strictly regular.
========================================================================

8. Consider a regular language L = {w: |na(w) mod 2 = 0 and nb(w) mod 2 = 0}. Which of the following grammar is regular grammar for L? (a) S aA| bB|λ A aS| bC|λ B aC|bS C aB|bA (b) S aA| bB|λ A aS| bC|λ B aC|bS C aB|bA|λ (c) S aA| bB|λ A aS| bC B aC|bS C aB|bA (d) S bA| aB|λ A aS| bC B aC|bS C aB|bA

Explanation:

Understanding the Language:

$n_a(w) \mod 2 = 0$ means the number of 'a's in the string must be even.
$n_b(w) \mod 2 = 0$ means the number of 'b's in the string must be even.
Therefore, the strings in $L$ must contain an even number of 'a's and an even number of 'b's.

========================================================================

9. Which of the following languages cannot be accepted by an NFA? (i) {akn | n, k ≥ 0 and n is multiple of k} (ii) {(ab)n | n ≥ 0}.{an | n ≥ 0} (iii) {anbbam | n, m ≥ 0} (iv) {anbban | n ≥ 0}

Explanation:

To determine which of the given languages cannot be accepted by a Non-deterministic Finite Automaton (NFA), we need to analyze whether each language is regular. NFAs can accept all regular languages, but they cannot accept languages that are non-regular.

(i) $L_1 = \{ a^k b^n \ | \ n, k \geq 0 \text{ and } n \text{ is a multiple of } k \}$

This language places a constraint that the number of 'b's ( $n$ ) must be a multiple of the number of 'a's ( $k$ ). This requires counting and comparing the numbers of 'a's and 'b's, which is a property that a regular language (and hence an NFA) cannot handle.
Conclusion: $L_1$ is not regular and cannot be accepted by an NFA.

(ii) $L_2 = \{ (ab)^n \ | n \geq 0 \} \cdot \{ a^n \ | n \geq 0 \}$

This language consists of two parts: $(ab)^n$ , which repeats the string "ab" $n$ times, followed by a string of $n$ 'a's. This is similar to the language $\{ a^n b^n \}$ , which is known to be non-regular because it requires counting and matching the numbers of 'a's and 'b's.
Conclusion: $L_2$ is not regular and cannot be accepted by an NFA.

(iii) $L_3 = \{ a^n b b a^m \ | n, m \geq 0 \}$

This language allows any number of 'a's followed by two 'b's and then followed by any number of 'a's. There are no dependencies between the counts of 'a's before and after the 'b's, so this language is similar to a regular expression like $a^* bb a^*$ , which is regular.
Conclusion: $L_3$ is regular and can be accepted by an NFA.

(iv) $L_4 = \{ a^n bb a^n \ | n \geq 0 \}$

This language requires an equal number of 'a's before and after two 'b's, which requires counting and matching. This is similar to the classic non-regular language $\{ a^n b^n \}$ , which cannot be handled by a regular language or an NFA.
Conclusion: $L_4$ is not regular and cannot be accepted by an NFA.

Final Conclusion:

The languages that cannot be accepted by an NFA are:

$L_1 = \{ a^k b^n \ | \ n, k \geq 0 \text{ and } n \text{ is a multiple of } k \}$
$L_2 = \{ (ab)^n \ | n \geq 0 \} \cdot \{ a^n \ | n \geq 0 \}$
$L_4 = \{ a^n bb a^n \ | n \geq 0 \}$

Thus, the correct answer is (c) i, ii, iv only

========================================================================

10. Which of the following language is/are regular? 1. L = {yxy : x, y {0, 1}*, |y| = 3}, 2. L = {1k : k is either a multiple of 5 or a multiple of 7} 3. L = {1k : k is a multiple of 5, but not a multiple of 7}

Explanation:

1. $L_{1} = {y x y ∣ x, y \in {0, 1}^{*}, ∣ y ∣ = 3}$

Here, $y$ is a string of exactly 3 characters, and $x$ is any string from the alphabet $\{0, 1\}^*$ . So, the structure of the strings in $L_{1}$ is $y x y$ , where $y$ is always 3 characters long.
Since the length of $y$ is fixed (3), and regular languages can handle strings of fixed length, this language can be expressed as a regular expression. A regular expression for this could be: $(000 + 001 + 010 + 011 + 100 + 101 + 110 + 111)$ This describes a string with 3 fixed characters, followed by any string, followed by the same 3 characters.
Conclusion: $L_{1}$ is regular.

2. $L_{2} = {1^{k} ∣ k is either a multiple of 5 or a multiple of 7}$

This language contains strings of '1's where the length is a multiple of 5 or 7. A regular language can recognize multiples of a specific number. For example, a DFA can be constructed to accept strings whose length is divisible by 5 or 7 by using separate cycles for multiples of 5 and 7.
This is a union of two regular languages (multiples of 5 and multiples of 7), and the union of two regular languages is also regular.
Conclusion: $L2$ is regular.

3. $L_{3} = {1^{k} ∣ k is a multiple of 5 but not a multiple of 7}$

This language includes strings whose length is divisible by 5 but not divisible by 7. The set of multiples of 5 is regular, and the set of multiples of 7 is also regular. The difference between two regular languages (multiples of 5 minus multiples of 7) is regular because regular languages are closed under difference operations.
Conclusion: $L_{3}$ is regular.

Final Conclusion:

All three languages are regular. The correct answer is all are regular.

=======================================================================

11. Which of the following language is/are not regular? 1. L = {anbm : n ≤1000 and m>20} 2. L = {anbm : n + m is even but n is not prime} 3. L = {anbm : n is square of m and n<1000} 4. L = {anbm : n is square of m or n<1000}

Explanation:

1. $L_1 = \{ a^n b^m \ | \ n \leq 1000 \text{ and } m > 20 \}$

The condition $n \leq 1000$ restricts $n$ to a finite set of values (from 0 to 1000). Finite constraints like this can be handled by a regular language.
The condition $m > 20$ can also be expressed as a regular language because we can construct a DFA that starts accepting strings with $m \geq 21$ .
Since both conditions can be handled by a DFA, and the combination of finite constraints and regular constraints can still be regular, this language is regular.

2. $L_2 = \{ a^n b^m \ | \ n + m \text{ is even and } n \text{ is not prime} \}$

The condition $n + m \text{ is even}$ can be handled by a DFA because it's a simple condition based on counting.
However, checking whether $n$ is not prime introduces complexity. Determining whether a number is prime is a non-trivial task that requires more computational power than what a DFA can provide. A DFA cannot count or perform arithmetic operations like checking for primality.
Conclusion: $L_2$ is not regular because checking for primes requires more power than a regular language can handle.

3. $L_{3} = {a^{n} b^{m} ∣ n is the square of m and n < 1000}$

The condition $n \text{ is the square of } m$ requires comparing the two numbers in a specific mathematical way (i.e., $n = m^2$ ). Regular languages are not capable of handling arithmetic relationships like squaring numbers.
However, the condition $n < 1000$ only restricts $n$ to a finite range, which is regular.
Conclusion: $L_3$ is not regular because checking if $n = m^2$ involves arithmetic, which cannot be handled by a DFA.

4. $L_{4} = {a^{n} b^{m} ∣ n is the square of m or n < 1000}$

This language includes two parts:
1. $n \text{ is the square of } m$ , which as discussed in $L_3$ , is not regular.
2. $n < 1000$ , which is a finite restriction and is regular.
The union of a non-regular language and a regular language is still non-regular.
Conclusion: $L_4$ is not regular because it includes the non-regular part from $n = m^2$ .

Final Conclusion:

The languages that are not regular are:

$L_2 = \{ a^n b^m \ | \ n + m \text{ is even and } n \text{ is not prime} \}$
$L_4 = \{ a^n b^m \ | \ n \text{ is the square of } m \text{ or } n < 1000 \}$

Thus, the correct answer is that $L_2$ , $L_3$ , and $L_4$ are not regular.

=====================================================================

12. If L is regular language over Σ then which of the following language is/are regular? I. LeftSide(L) = {w : wwR L} II. Insert(L) = {uav : a  Σ, uv L}

Explanation:

. $LeftSide (L) = {w : w w^{R} \in L}$

$w^R$ denotes the reverse of string $w$ .
This language consists of strings $w$ such that concatenating $w$ with its reverse results in a string belonging to the regular language $L$ .
Checking whether $ww^R \in L$ involves both reversing a string and matching it against a regular language $L$ . This introduces the need for context-sensitive processing because determining if a string is followed by its reverse typically requires remembering the entire string $w$ , which is beyond the capability of regular languages and DFAs.
Conclusion: $\text{LeftSide}(L)$ is generally not regular because it requires more computational power than a regular language can provide.

II. $\text{Insert}(L) = \{ uav : a \in \Sigma, uv \in L \}$

This language is constructed by inserting a single character $a \in \Sigma$ into a string in $L$ , resulting in a new string $uav$ where $uv \in L$ .
Inserting a single character into a string and checking if the resulting string is part of $L$ does not add complexity beyond regularity. A DFA could be extended to simulate this process by remembering the point of insertion and continuing to check if the resulting string belongs to $L$ .
Since regular languages are closed under operations such as concatenation, insertion of a character does not break regularity.
Conclusion: $\text{Insert}(L)$ is regular.

Final Conclusion:

$\text{LeftSide}(L)$ is not regular.
$\text{Insert}(L)$ is regular.

Therefore, the correct conclusion is that only $\text{Insert}(L)$ is regular.

======================================================================

13. Which of the following statement is/are true? 1. If complement of L is non-regular then L is also non-regular. 2. If L* is regular then L must be regular. 3. If L1  L2 is regular then at least one of them (i.e. L1 or L2) must be regular. 4. If L1 is regular and L2 is non-regular language then L1 – L2 is not regular.

Explanation:

1. If the complement of $L$ is non-regular, then $L$ is also non-regular.

False: This statement is not necessarily true. There are cases where a language is regular, but its complement is non-regular, or vice versa. For example, consider the language $L = \{ a^n b^n \ | \ n \geq 0 \}$ , which is non-regular, but its complement is non-regular too. However, in general, regular languages are closed under complement, meaning if a language is regular, so is its complement. But the statement suggests the reverse, which is incorrect.

2. **If $L^*$ is regular, then $L$ must be regular.**

True: This statement is correct. The star operation ( $L^*$ ) applied to a regular language always results in a regular language. If $L^*$ is regular, $L$ itself must also be regular because the Kleene star of a non-regular language would not result in a regular language.

3. If $L_1 \cup L_2$ is regular, then at least one of $L_1$ or $L_2$ must be regular.

False: This statement is not true. It is possible for the union of two non-regular languages to be regular. For example, consider $L_1 = \{ a^n b^n \}$ and $L_2 = \{ a^n b^{2n} \}$ , both of which are non-regular, but their union $L_1 \cup L_2 = \{ a^n b^m \ | \ n = m \text{ or } m = 2n \}$ could be regular in certain cases depending on the structure. Regular languages are not always decomposable into regular components.

4. If $L_1$ is regular and $L_2$ is non-regular, then $L_1 - L_2$ is not regular.

True: This is generally true. The difference between a regular language $L_1$ and a non-regular language $L_2$ is typically not regular. This is because regular languages are closed under certain operations (like union and intersection), but when we subtract a non-regular language from a regular one, we lose the regularity. The non-regular part could introduce complexities that break the regularity.

Final Conclusion:

True statements: 2 and 4
False statements: 1 and 3

====================================================================

14. Let L1, L2 & L3 are three regular languages, then which of the following language is/are regular? 1. L = {w : wL1 and wRL2, but wL3} 2. L = {w : wL2 or wRL3} 3. L = {w : w  (L1L2) but w(L1L2)} 4. L = {w :w(L1L2) but wR(L1.L3)}

Explanation:

1. $L = \{ w : w \in L_1 \text{ and } w^R \in L_2, \text{ but } w \notin L_3 \}$

This language requires that $w$ belongs to $L_1$ , the reverse of $w$ belongs to $L_2$ , and $w$ is not in $L_3$ .
Regular languages are not closed under reversal, meaning checking if $w^R \in L_2$ introduces complexity. The combination of checking both $w$ and $w^R$ , along with the exclusion from $L_3$ , means this language likely involves more computational complexity than a DFA can handle.
Conclusion: This language is not regular.

2. $L = {w : w \notin L_{2} or w^{R} \notin L_{3}}$

The complement of a regular language is regular because regular languages are closed under complement. Checking if $w^R \notin L_3$ introduces complexity (since reversal is not always regular), but since the condition is a disjunction ("or"), it can still be regular in some cases.
However, the condition involving $w^R \notin L_3$ makes it non-trivial, and combining these checks can make the language non-regular.
Conclusion: This language is not regular.

3. $L = {w : w \in (L_{1} \cup L_{2}) but w \notin (L_{1} \cap L_{2})}$

$(L_1 \cup L_2)$ and $(L_1 \cap L_2)$ are both regular operations because regular languages are closed under union and intersection.
The difference between two regular languages (i.e., $(L_1 \cup L_2) \setminus (L_1 \cap L_2)$ ) is also regular because regular languages are closed under difference.
Conclusion: This language is regular.

4. $L = \{ w : w \notin (L_1 \cap L_2) \text{ but } w^R \in (L_1 . L_3) \}$

The language involves checking if $w^R \in (L_1 . L_3)$ , which is a concatenation operation. While regular languages are closed under concatenation, the inclusion of $w^R$ again introduces complexity.
Since reversal is not a regular operation, this language likely requires more computational resources than a DFA can provide, making it non-regular.
Conclusion: This language is not regular.

Final Conclusion:

Regular language: 3
Non-regular languages: 1, 2, 4

====================================================================

15. Which of the following statement/s is/are false? I. If L1L2 is regular and complement of L1 is not regular then L2 is always nonregular. II. There exists two distinct non-regular language L1 & L2, for which L1* UL2* is regular. III. If L1, L2 and L3 are regular language then L1. (L2  L3) = L1.L2  L1.L3 (a)I & II only (b) I & III only (c) I only (d) II & III only

Explanation:

I. If $L_1 \cap L_2$ is regular and the complement of $L_1$ is not regular, then $L_2$ is always non-regular.

This statement is false. The fact that $\text{complement}(L_1)$ is not regular doesn't necessarily imply anything about $L_2$ . For example, it is possible for $L_1$ to be non-regular, $L_2$ to be regular, and $L_1 \cap L_2$ to still be regular (depending on their structure). Hence, the regularity of $L_2$ cannot be inferred solely from this condition.

II. **There exist two distinct non-regular languages $L_1$ and $L_2$ for which $L_1^* \cup L_2^*$ is regular.**

This statement is true. It is possible to have two non-regular languages $L_1$ and $L_2$ , but their star-closure or union results in a regular language. For example, consider two non-regular languages where their star-closure results in periodic patterns that can be recognized by a finite automaton. A specific example would be carefully crafted languages whose star operations lead to a regular union.

III. If $L_1$ , $L_2$ , and $L_3$ are regular languages, then $L_1 \cdot (L_2 \cap L_3) = (L_1 \cdot L_2) \cap (L_1 \cdot L_3)$

This statement is true. Regular languages are closed under concatenation and intersection, and the distributive property holds for regular languages. Thus, this equality is correct: concatenating $L_1$ with the intersection of $L_2$ and $L_3$ is the same as taking the intersection of the concatenations $L_1 \cdot L_2$ and $L_1 \cdot L_3$ .

Final Conclusion:

False statements: I
True statements: II and III

=====================================================================

16. How many of the following language is/arenon-regular? _________ 1. L = {anak : n >=0 and k is perfect square} 2. L = {ak : k is prime or k is even} 3. L = {ak : k is prime or k is product of at least two prime numbers} 4. L = {ak : k is multiple of 4 or k is odd}

Explanation:

1. $L = {a^{n} a^{k} : n \geq 0 and k is a perfect square}$

This language involves a condition where $k$ must be a perfect square. Recognizing perfect squares requires counting and comparison that a finite automaton (which can only remember a finite number of states) cannot handle.
Conclusion: This language is non-regular.

2. $L = {a^{k} : k is prime or k is even}$

The language involves recognizing prime numbers, which is not possible with a finite automaton because checking for primes requires unbounded counting and complex comparison. However, checking if $k$ is even is simple (can be done by a DFA).
Since the prime condition makes this language too complex for a regular language, this language is non-regular.
Conclusion: This language is non-regular.

3. $L = {a^{k} : k is prime or k is a product of at least two prime numbers}$

Recognizing prime numbers is not feasible for a regular language, and recognizing the product of primes (which involves factorization) is also a non-regular task, as it requires complex computation that DFAs cannot perform.

Conclusion: This language is non-regular.

4. $L = {a^{k} : k is a multiple of 4 or k is odd}$

This language is regular because both "multiple of 4" and "odd" are simple modular conditions that a DFA can handle. A DFA can easily track whether $k$ is a multiple of 4 (by cycling through states) or odd.
Conclusion: This language is regular.

Final Conclusion:

Non-regular languages: 1, 2, and 3
Regular language: 4

==========================================================================

17. Which of the following statements is/are True?
(a) The intersection of a context free language with a regular language is context free.
(b) The intersection of non-regular language and context free language is always non-regular language. (c) The concatenation of a context free language and the complement of a regular language is context free. (d) The concatenation of two non-regular languages may be a regular language
======================================================================

18. Which of the following statements is/are False?
(a) If L is context-free language and M is DCFL then L – M is CFL.
(b) If L is DCFL and M is CFL then L – M is CFL.
(c) If L and M are DCFL then 𝐿 ∩ 𝑀 is CFL.
(d) The subset of a decidable language is always decidable.

==========================================================================

Search This Blog

Wikipedia

Search

Main header

2nd header links

TOC - Decidability and Undecidability problems

Must Learn Coding Questions For Interview

TOC Questions

Context-Free Grammar (CFG):

Rules analysis:

Context-Free Grammar (CFG) - Type 2:

(i) {akn∣n,k≥0 and n is a multiple of k}

(ii) {(ab)n∣n≥0}⋅{an∣n≥0}

(iii) {anbbam∣n,m≥0}

(iv) {anbban∣n≥0}

Statement 1:

Statement 2:

Statement 3:

Statement 4:

Conclusion:

Final Answer:

1. S→Saaa ∣ aS ∣ a

2. S→aaS ∣ bS ∣ λ

3. S \rightarrow aS \ | \ bbS \ | \ \lambdaS→aS ∣ bbS ∣ λ

4. S→aS ∣ bSb ∣ λ

Conclusion:

Understanding the Language:

(i) L1={akbn ∣ n,k≥0 and n is a multiple of k}L_1 = \{ a^k b^n \ | \ n, k \geq 0 \text{ and } n \text{ is a multiple of } k \}L1​={akbn ∣ n,k≥0 and n is a multiple of k}

(ii) L2={(ab)n ∣n≥0}⋅{an ∣n≥0}L_2 = \{ (ab)^n \ | n \geq 0 \} \cdot \{ a^n \ | n \geq 0 \}L2​={(ab)n ∣n≥0}⋅{an ∣n≥0}

(iii) L3={anbbam ∣n,m≥0}L_3 = \{ a^n b b a^m \ | n, m \geq 0 \}L3​={anbbam ∣n,m≥0}

(iv) L4={anbban ∣n≥0}L_4 = \{ a^n bb a^n \ | n \geq 0 \}L4​={anbban ∣n≥0}

Final Conclusion:

1. L1={yxy ∣ x,y∈{0,1}∗,∣y∣=3}

2. L2={1k ∣ k is either a multiple of 5 or a multiple of 7}

3. L3={1k ∣ k is a multiple of 5 but not a multiple of 7}

Final Conclusion:

1. L1={anbm ∣ n≤1000 and m>20}L_1 = \{ a^n b^m \ | \ n \leq 1000 \text{ and } m > 20 \}

2. L2={anbm ∣ n+m is even and n is not prime}L_2 = \{ a^n b^m \ | \ n + m \text{ is even and } n \text{ is not prime} \}

3. L3={anbm ∣ n is the square of m and n<1000}

4. L4={anbm ∣ n is the square of m or n<1000}

Final Conclusion:

. LeftSide(L)={w:wwR∈L}

II. Insert(L)={uav:a∈Σ,uv∈L}\text{Insert}(L) = \{ uav : a \in \Sigma, uv \in L \}

Final Conclusion:

1. If the complement of LL is non-regular, then LL is also non-regular.

2. If L∗L^* is regular, then LL must be regular.

3. If L1∪L2L_1 \cup L_2​ is regular, then at least one of L1L_1​ or L2L_2​ must be regular.

4. If L1L_1​ is regular and L2L_2 is non-regular, then L1−L2L_1 - L_2​ is not regular.

Final Conclusion:

1. L={w:w∈L1 and wR∈L2, but w∉L3}L = \{ w : w \in L_1 \text{ and } w^R \in L_2, \text{ but } w \notin L_3 \}

2. L={w:w∉L2 or wR∉L3}

3. L={w:w∈(L1∪L2) but w∉(L1∩L2)}

4. L={w:w∉(L1∩L2) but wR∈(L1.L3)}L = \{ w : w \notin (L_1 \cap L_2) \text{ but } w^R \in (L_1 . L_3) \}

Final Conclusion:

I. If L1∩L2L_1 \cap L_2 is regular and the complement of L1L_1​ is not regular, then L2L_2​ is always non-regular.

II. There exist two distinct non-regular languages L1L_1​ and L2L_2​ for which L1∗∪L2∗L_1^* \cup L_2^*​ is regular.

III. If L1L_1, L2L_2​, and L3L_3​ are regular languages, then L1⋅(L2∩L3)=(L1⋅L2)∩(L1⋅L3)L_1 \cdot (L_2 \cap L_3) = (L_1 \cdot L_2) \cap (L_1 \cdot L_3)

Final Conclusion:

1. L={anak:n≥0 and k is a perfect square}

2. L={ak:k is prime or k is even}

3. L={ak:k is prime or k is a product of at least two prime numbers}

Recognizing prime numbers is not feasible for a regular language, and recognizing the product of primes (which involves factorization) is also a non-regular task, as it requires complex computation that DFAs cannot perform.

4. L={ak:k is a multiple of 4 or k is odd}

Final Conclusion:

Popular Post

MindMaps

Featured post

Question 1: Reverse Words in a String III

Labels

(i) ${a^{k} n ∣ n, k \geq 0 and n is a multiple of k}$

(ii) ${(a b)^{n} ∣ n \geq 0} \cdot {a^{n} ∣ n \geq 0}$

(iii) ${a^{n} b b a^{m} ∣ n, m \geq 0}$

(iv) ${a^{n} b b a^{n} ∣ n \geq 0}$

1. $S \to S aaa ∣ a S ∣ a$

2. $S → aa S ∣ b S ∣ λ$

3. $S \rightarrow aS \ | \ bbS \ | \ \lambda$

4. $S → a S ∣ b S b ∣ λ$

(i) $L_1 = \{ a^k b^n \ | \ n, k \geq 0 \text{ and } n \text{ is a multiple of } k \}$

(ii) $L_2 = \{ (ab)^n \ | n \geq 0 \} \cdot \{ a^n \ | n \geq 0 \}$

(iii) $L_3 = \{ a^n b b a^m \ | n, m \geq 0 \}$

(iv) $L_4 = \{ a^n bb a^n \ | n \geq 0 \}$

1. $L_{1} = {y x y ∣ x, y \in {0, 1}^{*}, ∣ y ∣ = 3}$

2. $L_{2} = {1^{k} ∣ k is either a multiple of 5 or a multiple of 7}$

3. $L_{3} = {1^{k} ∣ k is a multiple of 5 but not a multiple of 7}$

1. $L_1 = \{ a^n b^m \ | \ n \leq 1000 \text{ and } m > 20 \}$

2. $L_2 = \{ a^n b^m \ | \ n + m \text{ is even and } n \text{ is not prime} \}$

3. $L_{3} = {a^{n} b^{m} ∣ n is the square of m and n < 1000}$

4. $L_{4} = {a^{n} b^{m} ∣ n is the square of m or n < 1000}$

. $LeftSide (L) = {w : w w^{R} \in L}$

II. $\text{Insert}(L) = \{ uav : a \in \Sigma, uv \in L \}$

1. If the complement of $L$ is non-regular, then $L$ is also non-regular.

2. **If $L^*$ is regular, then $L$ must be regular.**

3. If $L_1 \cup L_2$ is regular, then at least one of $L_1$ or $L_2$ must be regular.

4. If $L_1$ is regular and $L_2$ is non-regular, then $L_1 - L_2$ is not regular.

1. $L = \{ w : w \in L_1 \text{ and } w^R \in L_2, \text{ but } w \notin L_3 \}$

2. $L = {w : w \notin L_{2} or w^{R} \notin L_{3}}$

3. $L = {w : w \in (L_{1} \cup L_{2}) but w \notin (L_{1} \cap L_{2})}$

4. $L = \{ w : w \notin (L_1 \cap L_2) \text{ but } w^R \in (L_1 . L_3) \}$

I. If $L_1 \cap L_2$ is regular and the complement of $L_1$ is not regular, then $L_2$ is always non-regular.

II. **There exist two distinct non-regular languages $L_1$ and $L_2$ for which $L_1^* \cup L_2^*$ is regular.**

III. If $L_1$ , $L_2$ , and $L_3$ are regular languages, then $L_1 \cdot (L_2 \cap L_3) = (L_1 \cdot L_2) \cap (L_1 \cdot L_3)$

1. $L = {a^{n} a^{k} : n \geq 0 and k is a perfect square}$

2. $L = {a^{k} : k is prime or k is even}$

3. $L = {a^{k} : k is prime or k is a product of at least two prime numbers}$

4. $L = {a^{k} : k is a multiple of 4 or k is odd}$