710 views
2 votes
2 votes

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$

1 Answer

Best answer
5 votes
5 votes

$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. 

edited by

Related questions

1 votes
1 votes
3 answers
1
1 votes
1 votes
2 answers
3
akash.dinkar12 asked May 12, 2019
1,270 views
Consider a $5$-stage instruction pipeline. The stages and the corresponding stage delays are given below.$$\begin{array}{|l|l|}\hline \textbf{Instruction}&\textbf{Stage d...