Applied Course | Mock GATE | Test 1 | Question: 13

Question

Which of the following statement is not correct?

• A. $a^nb^nc^m$ is not CFG
• B. $a^mb^nc^n$ is deterministic CFG
• C. $a^nb^n$ is CFG
• D. $a^{800}b^{800}c^{800}$ is CFG

Comments

@Applied CourseIf we were to draw DFA for option D, we will get 2400 states right ??

---

No. 2401. (like a^2 will require 2 + 1 = 3 state, a^3 will require 3 + 1 = 4 state . and so on)

since states are finite option d is correct as it is regular language. ( regular languages are also accepted by CFG.)

if option is like a^n b^n c^n  then it is CSL which would not been accepted by CFG.

---

we need 2401 states not 2400

---

For dead state??

---

we need 1 extra state for accepting. like for accepting aa we need 3 states.

state 1 -> a -> state 2 -> a -> accept state.

---

But what about a dead state??is it not required here??like after b ,a should not cone

---

2401 states for NFA and 2402 for DFA.

---

Cool....got it👍

---

we need to check whether language is regular or not so we can check it by making NFA or DFA.

Answer 1

(A) $\rightarrow a^n b^n c^m$  is not CFG. NOT correct. $a^n b^n c^m$ is accepted by one stack PDA and generated by CFG.
(B) $\rightarrow a^m b^n c^n$ is deterministic CFG (TRUE)(CORRECT). $a^m b^n c^n$ is accepted by one stack PDA and generated by CFG.
(C) $\rightarrow a^n b^n$ is CFG - TRUE. (CORRECT). $a^n b^n$ is accepted by one stack PDA and generated by CFG.
(D) $\rightarrow a^{800}b^{800} c^{800}$ is CFG - TRUE (CORRECT).

Comments

a^n b^n c^n  is csl right ? . in some questions statement d is false

---

a^n b^n c^n  is csl  if n can take any value. but if n value is specific like n =800. then it is regular.

---

got it thanks bro