ISI 2021 | PCB CS | Question: 8

Question

Consider the following language $L$ over the alphabet $\Sigma=\{a, b, c\}$. $$ L=\left\{a^{i} b^{j} c^{k} \mid i, j, k \geq 0 \text {, and if } i=1 \text { then } j=k\right\} $$

1. Show that $L$ is not regular.
2. Show that $L$ is a context-free language.

Answer 1

ans

Answer 2

i) To show that L is not a regular language, we can use the pumping lemma for regular languages. Assume that L is regular and let p be the pumping length given by the lemma. Consider the string s = a^pb^pc^p. Since |s| = 3p ≥ p, there exists a decomposition s = xyz, where |xy| ≤ p and |y| ≥ 1, such that xy^iz ∈ L for all i ≥ 0.

Since |xy| ≤ p, the substring y consists of only a's, only b's, or a combination of a's and b's. If y consists of only a's or only b's, then pumping y will either increase the number of a's or the number of b's, breaking the condition that i=1 implies j=k. If y consists of a combination of a's and b's, then pumping y will cause the number of a's and the number of b's to become unequal, again breaking the condition that i=1 implies j=k.

Therefore, we have a contradiction, and L cannot be a regular language.

ii) To show that L is a context-free language, we can construct a context-free grammar (CFG) that generates it. One possible CFG is:

S → aSc | A A → aAb | B B → bBc | ε

The production rules generate strings of the form a^ib^jc^k where i, j, and k are non-negative integers. The rule S → aSc generates strings with any number of a's and c's between a prefix of a's and a suffix of c's, while the rule S → A generates strings with an equal number of b's and c's.

The rule A → aAb generates strings with any number of a's and b's between a prefix and suffix of a's, while the rule A → B generates strings with an equal number of a's and b's. Finally, the rule B → bBc generates strings with any number of b's and c's between a prefix of b's and a suffix of c's, while the rule B → ε generates the empty string.

Since L can be generated by a CFG, it is a context-free language.

Comments

@Priyotosh2001 Bro did you appear for isi exam

Answer 3

a) What should be the Standard mode of answer this type of questions??
So if you saw my previous year PCB questions solves I follow the same method  

Pumping Lemma

Any language having string w with  | w | ≥ pumming length p        and   w = xyz such that   |xy |  ≤ p  ,   |y| ≥ 1   for all k ≥ 0 

xy^kz  is in L   . If not ,then w is not in L 

ans so L is not REGULAR . 

Pumping Lemma is a failing test , so whenever  we need to prove "not REGULAR" condition so always use this 

Choosing a string 

if  i = 1 and then j = k \( \rightarrow \) suggests a dependency between the no. of b's and c's when there is exactly one a

Let i = 1 and exploit this constraint   \( s = ab^pc^p \)    [ \(i = 1 , j = p , k = p\) ]  and \( j = k = p \) 

\[ s \in L \ \ \ \ \ \ \  \ \ \ \ \ \ \  \ \text{         |S| = 1+p+p = 2p +1} \geq p \ \ \ \ \ \ \ \ \  \ \ \ \ \ \  \ p \leq |s| = n\]   

Condition to be satisfied : \( A \rightarrow B   :  if \ i=1 \  then \ j=k\)

Applying Pumping Lemma

\( s = ab^pc^p    \rightarrow \) first P symbols are   \( ab^{p-1}\)

case i)  \( y = a \) \( x =\epsilon , y = a , z = b^pc^p\) pump \( k = 2\) \(xy^2z = \epsilon (a)^2b^pc^p = a^2b^pc^p\) i=2 and j=k=p               Since i=2 \( \not = 1 \) condition failed for A so overall  condition\( A \rightarrow B\) is true no restriction on j and k  \( \therefore\ a^2b^pc^p \in L \)  also pump \( k = 0\) \(xy^0z = \epsilon (a)^0b^pc^p = b^pc^p\) i=0 and j=k=p               Since i=0 \( \not = 1 \) condition failed for A so overall  condition\( A \rightarrow B\) is true no restriction on j and k  \( \therefore\ b^pc^p \in L \)

case ii)  \( y = some \  b \) \( x=a, y = b^t , z=b^{p-t}c^p   \)      \(1 \leq t \leq p-1\) \(xyz = ab^tb^{p-t}c^p = s = ab^pc^p     \)     \(  |s| = 2p+1 \) pump \( k = 2\) \(xy^2z =  a(b^t)^2b^{p-t}c^p = ab^{p+t}c^p\) when i=1 then  \( j \not = k \)       overall  condition failed   \( A \rightarrow B\) is false       \( ab^{p+t}c^p \not = ab^{p}c^p \)    \(ab^{p+t}c^p \notin L\) pump \( k = 0\) \(xy^0z =  a(b^t)^0b^{p-t}c^p = ab^{p-t}c^p\) when i=1 then  \( j \not = k \)       overall  condition failed   \( A \rightarrow B\) is false       \( ab^{p-t}c^p \not = ab^{p}c^p \)    \(ab^{p-t}c^p \notin L\)

Pumping Lemma fails   as \( xy^kz  \ is \notin \  L \ \forall \ k\) ,     L is  Not REGULAR

---

ii) L is a CONTEXT FREE LANGUAGE

A language is Context free if it can be generated by a CFG or accepted by a Pushdown Automaton

\(i=0 \)        \( a^0b^jc^k  \)         any  \( j , k \geq 0 \)                  (no restriction)

\(i=1 \)       \( a^0b^jc^j  \)           where   \( j = k \geq 0 \)                  \(so, ab^jc^j\)

\(i \geq 2 \)        \( a^ib^jc^k  \)         any  \( j , k \geq 0 \)                  (no restriction)

\[ L = L_0 \cup L_1 \cup L_2 = \{b^jc^k | j,k \geq 0 \} \cup \{ ab^jc^j | j \geq 0 \} \cup \{ a^ib^jc^k | I \geq 2 , j , k \geq 0\}\]

 

incomplete .....