The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
151 views

Image may contain: text

asked in Theory of Computation by Veteran (50.5k points) | 151 views

1 Answer

0 votes

we know that

Regular grammar generates Regular Language ===> Accepted by Finite Automata.

CFG generates CFL ====> Accepted by PDA

 

but PDA = FA + 1 - Auxiliary Memory  = FA+stack

therefore if you are not using the memory of PDA it simply looks as FA.

 

∴ PDA can recognize the language which is generates by either CFG or RG 

answered by Veteran (55.7k points)

Related questions

0 votes
0 answers
1
+1 vote
1 answer
2
asked Apr 29, 2016 in Theory of Computation by Sanjay Sharma Veteran (50.5k points) | 108 views
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,894 questions
52,260 answers
182,165 comments
67,679 users