LGT Sheet

Q1

1. Words have two or more parts which share a common unknown variable which determines how long each part is.
2. $L=\{a^n{b}^m,n>m\}$

The Pumping Lemma (Theorem)

The Pumping Lemma says if $L\subseteq {\Sigma }^{\ast }$ is a regular language then there is some $p>0$ such that every word $w\in L$ of length $|w|\ge p$ can be written in the form $w=xyz$ for $x,y,z\in {\Sigma }^{\ast }$ such that:

• If $|xy|\le p$ and $|y|>0$,
• then $x{y}^{n}z\in L$ for all $n\ge 0$.

Link to original

3. Assume $L=\{a^n{b}^m,n>m\}$ is a regular language. 1. There is some $p>0$ such that every $w\in L$ and $|w|\ge p$. 2. We need to satisfy $|xy|\le p$ and $|y|>0$. 3. Decompose $w$ into $xyz$: 1. $x=a^{\alpha }$ ($\alpha \ge 0$) 2. $y=a^{\beta }$ ($\beta >0\because |y|>0$) 3. $z=a^{p-\alpha -\beta }{b}^p$ 4. Hence, $x{y}^{n}z\in L$ for all $n\ge 0$: $\begin{array}{rl}x{y}^{n}z& \equiv a^{\alpha }{a}^{\beta n}{a}^{p-\alpha -\beta }{b}^p\\ & \equiv a^{p+\beta n-\beta }{b}^p\end{array}$ 5. For this word to be in the language, the exponent of $a$ must be greater than the exponent of $b$. $\begin{array}{rl}p+\beta n-\beta & >p\\ \beta n-\beta & >0\\ \beta n& >\beta \\ n& >1\because \beta >0\end{array}$ However, we can pick a value of $n$ such as $0$ which gives us a word which is not in the language. This is a contradiction. 6. Hence, it is not a regular language.

4. Construct a Turing Machine that can accept your chosen lang. $L=\{a^n{b}^m,n>m\}$

digraph {
	label="TM (explicit reject)"
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; qaccept;
	node[shape=circle];
	init->q1
	
	# must start at a
	q1->q2 [label="a,_,>"]
	q1->qreject [label="b,_,-"]
	q1->qreject [label="_,_,-"]
 
	# seek through a
	q2->q2 [label="a,a,>"]
	q2->q3 [label="b,b,>"]
	q2->qaccept [label="_,_,-"]
 
	# seek through b
	q3->q3 [label="b,b,>"]
	q3->qreject [label="a,_,-"]
	q3->q4 [label="_,_,<"]
 
	# clear last cell and seek back to a
	q4->q5 [label="b,_,<"]
	q5->q5 [label="b,b,<"]
	q5->q6 [label="a,a,<"]
	q5->qreject [label="_,_,-"]
 
	# seek back to start
	q6->q6 [label="a,a,<"]
	q6->q1 [label="_,_,>"]
}

digraph {
	label="TM (implicit reject)"
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; qaccept;
	node[shape=circle];
	init->q1
	
	# must start at a
	q1->q2 [label="a,_,>"]
 
	# seek through a
	q2->q2 [label="a,a,>"]
	q2->q3 [label="b,b,>"]
	q2->qaccept [label="_,_,-"]
 
	# seek through b
	q3->q3 [label="b,b,>"]
	q3->q4 [label="_,_,<"]
 
	# clear last cell and seek back to a
	q4->q5 [label="b,_,<"]
	q5->q5 [label="b,b,<"]
	q5->q6 [label="a,a,<"]
 
	# seek back to start
	q6->q6 [label="a,a,<"]
	q6->q1 [label="_,_,>"]
}

Source Code

Run with https://turingmachinesimulator.com/.

name: Check if word is in language L = {a^nb^m, n>m}
init: q1
accept: qAccept

q1,a
q2,_,>

q1,b
qReject,_,-

q1,b
qReject,_,-

q2,a
q2,a,>

q2,_
qAccept,_,-

q2,b
q3,b,>

q3,b
q3,b,>

q3,a
qReject,_,-

q3,_
q4,_,<

q4,b
q5,_,<

q5,b
q5,b,<

q5,_
qReject,_,-

q5,a
q6,a,<

q6,a
q6,a,<

q6,_
q1,_,>

Question 2

Given the language over $\Sigma =\{m,\#\}$:

$$L=\{m^b{m}^b\#mmmm{m}^b,b=0,1,2,\dots \}$$

1. Show that $L$ is non-regular.

   The Pumping Lemma (Theorem)

   The Pumping Lemma says if $L\subseteq {\Sigma }^{\ast }$ is a regular language then there is some $p>0$ such that every word $w\in L$ of length $|w|\ge p$ can be written in the form $w=xyz$ for $x,y,z\in {\Sigma }^{\ast }$ such that:

   • If $|xy|\le p$ and $|y|>0$,
   • then $x{y}^{n}z\in L$ for all $n\ge 0$.

   Link to original

• Assume $L$ is regular.
• Hence there is some $p>0$ such that every word $w\in L$ of length $|w|\ge p$ can be written in the form $w=xyz$.
• Decompose $m^b{m}^b\#mmmm{m}^b$ into $xyz$ to satisfy $|xy|\le p$, $|y|>0$.
  • $x=m^{\alpha }$ ($\alpha \ge 0$)
  • $y=m^{\beta }$ ($\beta >0\because |y|>0$)
  • $z=m^{p-\alpha -\beta }{m}^p\#mmmm{m}^p$
• Hence, $x{y}^{n}z\in L$ for all $n\ge 0$, so substitute $xyz$:

$$\begin{array}{rl}x{y}^{n}z& \equiv m^{\alpha }{m}^{\beta n}{m}^{p-\alpha -\beta }{m}^p\#mmmm{m}^p\\ & \equiv m^{p+\beta n-\beta }{m}^p\#mmmm{m}^p\end{array}$$

• For this word to be in the language, the exponents of the first, second and last occurrence of $m$ must equal each other.

$$\begin{array}{rl}p+\beta n-\beta & =p\\ \beta n-\beta & =0\\ \beta n& =\beta \\ n& =1\end{array}$$

• If we pick, $n=2$, this does not hold, which is a contradiction.

2. The # character prevents this language from being regular, by splitting up the two parts of $m$.

Question 3

1. Design a Turing Machine $M$ with the properties:
   • at least one accepting computation on $w=001$
   • at least one rejecting computation on $w=001$
   • at least one non-terminating computation on $w^{\prime }=110$

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; qaccept;
	node[shape=circle];
	init->q1
	
	# 
}