Construct a PDA to accept the language

2.3k Views Asked by At

construct a PDA that accepts the language:

a) $L_1 = \{ a^k b^k c^i \mid k,i \ge 0 \}$

my answer is :

$$\begin{align*} &S\to AA\\ &A\to abc \mid ab \mid c \mid \lambda \end{align*}$$

b) $L_2 = \{ a^m b^{2m} \mid m \ge 0 \}$

my answer is :

$$\begin{align*} &S\to A \mid B \mid \lambda\\ &A\to a\mid aa\\ &B\to b \end{align*}$$

My question is, Is my answer is the what the question ask for? if not, could help me understand what exactly the question want?

2

There are 2 best solutions below

0
On BEST ANSWER

The first and biggest problem is that you haven’t answered the question: it asks for pushdown automata accepting the languages $L_1$ and $L_2$, but you’ve attempted to give context-free grammars generating the languages; that’s a different thing altogether.

Your context-free grammars are in any case very far from generating the languages in question. Your first grammar generates the language

$$\{abcabc,abcab,abcc,abc,ababc,abab,ab,cabc,cab,cc,c,\lambda\}\;.\tag{1}$$

The words in this language that are also in $L_1$ are $ab,abc,abcc,cc,c$, and $\lambda$; the other six words are not in $L_1$. On the other hand, $aabb$ is one of infinitely many words in $L_1$ that are not in $(1)$.

Similarly, your second grammar generates only the language

$$\{\lambda,a,aa,b\}\;,\tag{2}$$

and the only word in $(2)$ that is also in $L_2$ is $\lambda$. On the other hand, $abb$ and $aabbbb$ are two of the infinitely many words of $L_2$ that are not in $(2)$.

You need to begin by getting a better understanding of the two languages. $L_2$ consists of all words that start with a string of $a$s, which is then followed by a string of exactly twice as many $b$s. Thus,

$$\begin{align*} L_2&=\{\lambda,abb,aabbbb,aaabbbbbb,\ldots\}\\ &=\{a^mb^{2m}:m\ge 0\}\;, \end{align*}$$

just as in the problem statement.

$L_1$ consists of all words that start with a string of any number of $a$s, which is immediately followed by a string of exactly the same number of $b$s, which in turn is followed by a string of any number of $c$s. Thus, it’s impossible for a word in $L_1$ to have an $a$ that comes after a $b$ or $c$, or to have a $b$ that comes after a $c$: the $a$s are first, the $b$s are in the middle, and the $c$s are last. Thus, $L_1$ consists of the following words:

$$\begin{align*} &\lambda,c,cc,ccc,cccc,\ldots\\ &ab,abc,abcc,abccc,abcccc,\ldots\\ &aabb,aabbc,aabbcc,aabbccc,aabbcccc,\ldots\\ &aaabbb,aaabbbc,aaabbbcc,aaabbbccc,aaabbbcccc,\ldots\\ &\vdots \end{align*}$$

I’m not going to say anything about the pushdown automata here, because it’s not clear how far back the explanation should start. I suggest that after you’ve thought about this a bit and made a stab at coming up with at least one of the PDAs, you ask a new question if you’re still hazy on the subject.

0
On

I gave an explanation for constructing a PDA here.

A pushdown automaton is a a finite state machine with a stack. So can you design an algorithm where the only memory is the stack?

1) The usage of the stack comes into play in making sure the number of $a$'s and $b$'s are the same. So read in the $a$'s and push them onto the stack. For each $b$, pop an $a$ off the stack. Then read in the $c$'s and accept. This is the general idea. Now you should think about strings that are not of the form prescribed by $L_{1}$. The PDA needs to reject strings not in $L_{1}$.

2) The algorithm is similar to part (1) for making sure the number of $a$'s and $b$'s are the same. The difference is that you want to pop an $a$ for every $2$ $b$'s you read in.