ISI2018-PCB-CS4

Question

Let the valid moves along a staircase be $U$ (one step up) and $D$ (one step down). For example, the string $s = UUDU$ represents the sequence of moves as two steps up, then one step down, and then again one step up. Suppose a person is initially at the base of the staircase. A string denoting a sequence of steps that takes the person below the base is invalid. For example, the sequence $UUDDDU$ is invalid. Let $L$ be the language defined by the set of valid strings which represent scenarios in which the person never returns to the base of the staircase after the final step.

1. Show that $L$ is not regular
2. Write a context free grammar for accepting $L$

Answer 1

$L$ is Not regular and we can prove it using Pumping lemma for Regular languages. 

---

Using Pumping lemma for Regular languages to Show that $L$ is Not Regular :

Pumping lemma states a Deep Property that All Regular languages share. By Showing that a language does not have the property stated by Pumping lemma, we are guaranteed that It is Not Regular. 

Pumping Lemma(PL) is a necessary condition for Regular languages but not sufficient condition

i.e. All Regular languages must satisfy this condition and some Non-regular languages also satisfy this condition.

So, Regular Language → Satisfies Pumping Lemma

∴ Contrapositive statement is Doesn't Satisfy Pumping Lemma → Not Regular Language

---

Pumping lemma for Regular languages says

" If a language L is Regular,

then $\exists P \geq 1$, such that 

$\forall \,\,strings\,\,w \in L$, If $|w| \geq P$ then

$\exists x,y,z$, such that $w = xyz$

and $|xy| \leq P$

and $y \neq \in$ i.e. $|y| \geq 1$

and $\forall q \geq 0$, $xy^qz \in L$

---

In Words, If $L$ is regular, then there’s some magic number $P$(Called Pumping length). And if I take any string $w$ that is at least as long as $P$, then I can break it up into three parts $x, y, $and $z.$ Now, the length of $xy$ is less than or equal to $P$, and also the length of $y$ is greater than or equal to $1$ and less than or equal to $P$.

In very simple words, If $L$ is a regular language then there is some positive number $P$ associated with $L$ such that for all strings $w $ of length greater than or equal to $P$, we can find some non-empty sub-string $y$ in $w$ within the first $P$ symbols of $w$  such that when we repeat $y$ Zero or more times then the produced strings also belong to $L.$

---

Now coming to the given language $L,$ Let's assume that it is Regular language. Hence, It will satisfy the Pumping lemma stated above. 

So, There must be some positive number  $P$ associated with $L$ such that Pumping lemma satisfies. So, Let's say that Magic number (Pumping length) is $P.$ So, Now, For all string, $w$ with length $\geq P$ ,  We must be able to find some Non-empty substring $y$ of length at most $P$ within the first $P$ symbols of $w$ such that we can repeat that $y$ Zero or more times, producing the strings belonging to $L.$ 

So, Let's take string $w = U^{P+1}D^{P},$ Clearly, $w \in L.$  For this string if You take any Non-empty substring $y$ within the first $P$ symbols (i.e. $y$ must be made of $U's$ only) and if you repeat that $y$ Zero times (repeating $y$ Zero times is same as Removing $y$ from the string $w$) then the resulted string will NOT belong to $L.$ So, Whatever Pumping length $P$ you take, at least One string $w = U^{P+1}D^{P} $ I have shown you which Won't get Pumped.   

So, Pumping lemma is violated/Not Satisfied by $L.$ So, $L$ is Not Regular. 

So, We have shown that $L$ is Not Regular.

$\color{Red}{\text{Understand Complete Pumping Lemma, Crystal Clear:}}$

Here is Complete Pumping Lemma Lecture: https://youtu.be/8cdPjuYbIrU 

This Pumping Lemma lecture contains EVERYTHING about Pumping Lemma of Regular Languages, i.e. Proof, Examples, Variations, GATE PYQs, Finding minimum pumping length etc. Watch this lecture for Complete, Correct & Clear Understanding.

---

---

Using Myhill-Nerode Equivalence Relation to Show that $L$ is Not Regular :

I will Not be stating the Whole Myhill-Neorde Theorem here But only the Part that is required to Show that $L_2'$ is Non-Regular.

Theorem : Let $L ⊆ Σ ^∗$ be any language. Suppose there is an infinite set $S$ of strings such that $\forall x, y ∈ S (x \neq y), x \not\equiv _L y.$ That is, suppose $(∀x \neq y ∈ S)(∃z ∈ Σ ^∗ ) (Exactly \,\,\,one\,\,\, of \,\,\,the \,\,\,strings\,\,\, xz\,\,\, or\,\,\, yz\,\,\, belongs\,\,\, to\,\,\, L).$ Then $L$ is not a regular language. Here such set $S$ is called Distinctive set for $L.$

http://www.cse.buffalo.edu/~regan/cse396/CSE396MNT.pdf

For given language $L, $ Consider the set $S = \{U^nD | n \geq 1\}.$ This set will work as a distinctive set for $L.$  i.e. If you take any Two  different arbitrary string $x,y$ from $S$ then You will definitely find some $z \in \Sigma^*$ such that Exactly one of the Strings $xz$ or $yz$ will belong to $L.$ Let any pair $x, y ∈ S$ with $x \neq y $ be given. By definition of S, there are numbers $m, n ≥ 1$ with $m <  n$ such that $x = U^mD$ and $y = U^nD$ . Take $z = D^{m-1}.$ Then $xz$ will Not belong to $L$ But  $yz$ will belong to $L.$ Since $xz = U^mD^ m \notin L$ and $yz = U^nD^ m \in L(because $m <n$).$ Since $x, y ∈ S$ were arbitrary, $S$ is an “infinite distinctive set” for $L$, so $L$ is non-regular. (Here the boldface take goes with the $∃$ quantifer, while all the other boldface words go with the $∀$ quantifier.)

---

---

                                                                        PDA for the Given Language $L$

---

---

                                                                                             CFG for modified $L$

I am going to give the CFG for slightly different language here. 

Let $L'$ be the language of ALL Valid Strings i.e. I have removed the restriction of never returning to the base of the staircase after the final step. So, for this language $L'$ ,the CFG is as follows : 

$S \rightarrow ASD \,\,|\,\,SS\,\,|\,\,A\,\,|\,\,\in$

$A \rightarrow UA \,\,|\,\,U$   

Basic idea behind writing CFG for this language is that this language is somewhat similar to the language of Balanced parentheses. 

The grammar for Balanced Parentheses language is this : $S \rightarrow (S) | SS|\in$

(Refer below for Balanced Parentheses Grammar and language :

https://cs.stackexchange.com/questions/14557/language-of-balanced-parentheses-biconditional-proof-about-parentheses )

So, The very basic idea here is that Every $D$ has some $U's(One \,\,or\,\, more)$ associated to it and those $U's$ appears before that $D$.

So, Just modify the Balanced Parentheses Grammar (Let me call it BP henceforth) to have any positive number of $U's$ associated with every $D's .$ 

So, The Simplest Grammar will come out to be :

 $S \rightarrow ASD \,\,|\,\,SS\,\,|\,\,A\,\,|\,\,\in$

$A \rightarrow UA \,\,|\,\,U$   

You can see that it is very similar to BP but it allows as to have more than one $U's $ associated with every $D.$

(I will leave it to the reader to convince himself/herself that this indeed is the Grammar associated with the modified language)

---

---

P.S. : I will update CFG for the given language in the Question as soon as I find it. If someone has any suggestions, Do let me know. I am kind of stuck because of the extra condition of  "never returning to the base of the staircase after the final step. "

Maybe i am missing something trivial here or some small thing. 

Comments

If we remove S→ ∈ production then for every steps of finite length in the staircase we will not be generating strings of form U^n D^n |n>=0  

This U^n D^n format of strings actually a possibility for every finite length to come back again to base.

And other possibility of getting to base e.g UUDDDU will never arise since we cant go below the base.

Can we do like this??

Answer 2

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

(Total no of U - Total no of D ) ≥0 [only greater than 0 because , after final state , step must not be the base]

alphabet = {U,D}                and language L = { w ∈ {U,D}* | for every prefix of w    number. of U ≥  number. of D  and for entire  number. of U >  number. of D  }

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 . 

s=U^p+1D^p                   |w| = (p+1)+p = 2p+1 ≥ p  (since  p ≥ 1)

compute the height at each prefix:

after   U^p+1                                     height   p+1 ≥ 1 ≥ 0

then append D^p                           height   - -1

after U^p+1D^p                             height    (p+1) -  p  = 1 > 0                  So,  | s | ≥  p        and   s = xyz     and  |xy|  ≤ p  , |y| ≥ 1   for all k ≥ 0 

xy is within the initial U^p+1              [as |xy|  ≤ p <p+1]

So,  x = U^a (a≥0)       ,y =U^b (b≥1)      ,z=U^{(p+1 −a−b)}#1#10ⁿ             [as  a+b ≤ p < n ]

As Pumping Lemma 

pumped string  xy^kz = U^aU^(b)kU^{(p+1−a−b)}D^p    =    U^{(a + kb + p+1 − a − b)}D^p     =   U^{(p+1  + (k-1)b )}D^p

Pump with k=0 

S₀= xy⁰z = U^aU^(b)0U^{(p+1−a−b)}D^p    =    U^{(p+1 − b)}D^p     

^Now U^{(p+1 − 1)}D^p  = U^pD^p      [when b=1]

but when b  ≥ 2 

so , U^{(p+1 − b)}D^p     [when b≤ p  as a+b ≤ p]

after   U^p+1-b                                 height   p+1-b

then append D^p                           height   (p+1-b) -p = 1-b

since b ≥ 2   ,   1-b ≤ 1-2  = -1

after U^p+1D^p                             height    (p+1) -  p  = 1 > 0                  So,  | s | ≥  p        and   s = xyz     and  |xy|  ≤ p  , |y| ≥ 1   for all k ≥ 0 

In all cases (b=1 or b ≥ 2 )  xy⁰z ∈ L. Thus L is NOT REGULAR

---

b) Write a CONTEXT FREE GRAMMAR for accepting L

we need a Context Free Grammar (CFG) that generates string L i.e. strings where the height never goes below 0 and the final height is greater than 0 

Grammar production rule is :  S →  U |  US | SU | SDS

Correctness :

1. Never below 0: All string starts with U (since S derivatives begins with U or recurse to S) ensuring initial height  ≥ 1. In SDS , the first S ends > 0    D decreases height by 1 ( to ≥ 0)  and the second S starts from there ensuring never going below 0, maintaining validity.
2. Final height always > 0:

production: U:height 1 

SU, US: add 1 to an S with height >0

SDS: if first S has height h₁>0   and after D its become h₁ - 1 ≥ 0 , then second S adds h₂ > 0

total h₁ - 1 + h₂ > 0.