NIELIT 2016 MAR Scientist C - Section C: 13

Question

Context-free grammar can be recognized by 

• A. finite state automation
• B. $2$- way linear bounded automata
• C. push down automata
• D. both (B) and (C)

Comments

Same question

https://gateoverflow.in/53013/cfg

---

What is 2 way Linear Bounded automata? Is it same as LBA?

Answer 1

Context-free Grammar (CFG) can be recognized by both 2-way linear bounded automata and push down automata . 

regular --> dcfl --> ncfl --> Csl --> recursive -->recursive enumerable (implication)

Comments

but the question asked here is regarding CFG not CFL

---

2-way linear bounded automata , linear bounded automata both are same?

Answer 2

Automata	Recognized Grammar
Finite Automata	Regular Grammar
PDA	CFG
LBA	CSG
TM	REG

So Ans is B.

2-way LinearBounded Automata(it called so bcz Here TM's  Tapes both sides are restricted)

Comments

Unrestricted Grammar and RECURSIVE Enumerable grammar are same or not ??

---

same

Answer 3

(B)2 way Linear Bounded Automata

Reference:Context Sensitive grammar

Answer 4

Context free Grammar can be recognize by both Linear Bounded Automata (LBA) and Push down Automata (PDA).

Hence,Option (D)Both B and C is the correct choice.