CFL langauage

Question

How a^i b^j c^k |  i= j+k is CFL?

Please explain

Thanks

Comments

push an element into stack when a comes. then when b comes pop element from stack then when c comes pop element from stack. if stack is empty then string is accepted else rejected.

---

@Satbir 

i did not get .Can you please explain with example

---

imagine an empty stack

whenever a comes we apply push(a) operation on stack.

whenever b or c comes we apply pop(a) operation on stack.

if stack is empty at the end then string is accepted else rejected.

for eg:- a^2b^1c^1 

here first 2 char of string are aa so stack will have 2 as in it through push a operation.

then b comes so we pop a from stack => stack is left with only 1 a present in it.

then c comes so we again pop a from stack=> stack is empty

string input is now over and stack is empty =>string accepted

(please note that the ordering of a b and c will be done with the help of state transitions in the pda)

---

Corresponding PDA

---

@Satbir @arya_stark

In this scenario a^2 b^5 c^3  how you would have done the push and pop operation?

Please suggest

---

in the above diagram

initially stack contains z.

(a,b/c)-> when we see any input a and top of stack contains b then we remove b (pop b) from stack and then push c into the stack.

(a,b/E) -> when we see any input a and top of stack contains b then we remove b (pop b) from stack and push nothing into the stack.

(E,z/z) -> when there are no inputs and if we see z on top of stack then pop z from top of stack and then again push z back into the stack.(it indicates that stack is empty)

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

input:- a^2 b^5 c^3 = aabbbbbccc. here i != j+k so it will be rejected.

a-> (a,z/az) remain in state A. top of stack will now become a.

a->(a,a/aa) remain in state A. top of stack will now become a

b->(b,a/E) go to state B. one a will be removed from top of stack. top of stack will now become a

b->(b,a/E) remain in state B. one a will be removed from top of stack. top of stack will now become z

b-> (b,z/ ?) since this move is not defined in the diagram (i.e. what to do when we give an input b and top of stack contains z) the pda will not do anything and would halt.

=> PDA is rejected since we did not reached the final state on the given input.

 

 

 

---

@Mayankprakash 

for a^2b^5c^3

see 2 a's will pushed and then 2 b's will be pop out and we are in non final state and with end of the string so it will not accepted

---

@Mayankprakash

I think question is $a^i b^j c^k |  i= j+k$

                        Here $i=j+k $ not $j=i+k$....

Means no of $a's$ is equal to the sum of no of $b's$ and $c's$....

 

Answer 1

S->aSc/aAc

A->bAc/epsilon

Comments

@Ratul Chatterjee where is b in your grammer ?

Answer 2

From $i$=$j$+$k$ , we can say no.of $a's$ =no. of $b's$+ no.of $c's$.

With the help of stack, whenever we see $a's$ push them and pop $b's$ and $c's$. If the stack is empty string is accepted otherwise rejected.

So,with the help of this we can say given language is CFL. Particularly it's DCFL($Deterministic$  $  CFL$)