Context Free Language and Push Down Automata

Question 1

P is Regular and Q is Context Free.
P ^ Q is Regular?

Answer 1

No. P ^ Q is not regular

Question 2

P is Regular and Q is Context Free.
P - Q is Regular?

Answer 2

No. P - Q is not regular

Question 3

P is Regular and Q is Context Free.
P Compliment is Regular?

Answer 3

Yes. Complement of any regular language is regular.

Question 4

P is Regular and Q is Context Free.
Q Compliment is Regular?

Answer 4

NO. Context Free Languages are not closed under Compliment.

Question 5

P is Regular and Q is Context Free.
Q - P is Context Free?

Answer 5

Yes. Context Free Languages are closed under Intersection with Regular language.
Here Q - P can be written as ‘Q’ intersection ‘P compliment’

Question 6

CFL and REG both are closed under UNION
(T or F)?

Answer 6

TRUE

Question 7

CFL and REG both are closed under INTERSECTION
(T or F)?

Answer 7

FALSE. Only REG are closed under Intersection and not CFL.
i.e. REG intersection REG = REG
but CFL intersection CFL is NOT ALWAYS equal to CFL.

Question 8

CFL and REG both are closed under COMPLEMENT
(T or F)?

Answer 8

FALSE. Only REG are closed under COMPLEMENT and not CFL.
i.e. Complement of REG = REG
but Complement of CFL is NOT ALWAYS equal to CFL.

Question 9

CFL and REG both are closed under CONCATENATION
(T or F)?

Answer 9

TRUE

Question 10

L = {pow(a, p) | p is a prime number}
is this CFL?

Answer 10

NO. This is CSL(Context sensitive language). There exists a LBA that can be implemented to solve such question.

Question 11

What is Type - 0 Grammar?

Answer 11

Recursively Enumerable.
Automata = Turing Machine.

Question 12

What is Type - 1 Grammar?

Answer 12

Context Sensitive
Automata = Linear-bounded non-deterministic machine.

Question 13

What is Type - 2 Grammar?

Answer 13

Context Free
Automata = Non-deterministic push down automata

Question 14

What is Type - 3 Grammar?

Answer 14

Regular
Automata = Finite state automata

Question 15

What is the set order of Grammar?
i.e. A < B < C < D

Answer 15

REG < CFL < CSL < RE

Question 16

Recursively Enumerable (RE) is closed in all operations:
UNION
INTERSECTION
COMPLEMENT
CONCATENATION ( . )
KLEENE CLOSURE
POSITIVE KLEENE CLOSURE (+)

Answer 16

FALSE
RE is closed under all the given operations EXCEPT COMPLEMENT.
RE is not closed under Complement.

Question 17

Recursive (REC) is closed in all operations:
UNION
INTERSECTION
COMPLEMENT
CONCATENATION ( . )
KLEENE CLOSURE
POSITIVE KLEENE CLOSURE (+)

Answer 17

TRUE

Question 18

DCFL Union Regular is DCFL.
T or F

Answer 18

TRUE

Question 19

DCFL is closed under which operations?

Answer 19

COMPLEMENT
INVERSE HOMOMORPHISM
INTERSECTION with REG

REG = Regular Language, DCFL = Deterministic Context Free Language

Question 20

REG is closed under which operations?

Answer 20

UNION
INTERSECTION
COMPLEMENT
CONCATENATION ( . )
KLEENE CLOSURE
POSITIVE KLEENE CLOSURE (+)

REG = Regular Language

Question 21

RE is not closed under which operations?

Answer 21

COMPLEMENT.

RE = Recursively Enumerable Language

Question 22

CFL is not closed under which operations?

Answer 22

INTERSECTION,
COMPLEMENT.

CFL = Context Free Language

Question 23

REC is closed under which operation?

Answer 23

UNION
INTERSECTION
COMPLEMENT
CONCATENATION ( . )
KLEENE CLOSURE
POSITIVE KLEENE CLOSURE (+)

REC = Recursive Language

Question 24

CSL is closed under which operation?

Answer 24

UNION
INTERSECTION
COMPLEMENT
CONCATENATION ( . )
KLEENE CLOSURE
POSITIVE KLEENE CLOSURE (+)

CLS = Context Sensitive Language

Question 25

L = {ww | w ∈ {a,b}⋆}
L is CFL.
T or F ?

Answer 25

FALSE
L is Not CFL. But it’s Complement is CFL.

Question 26

The language accepted by Pushdown Automation in which the stack is limited to 10 items is best described as…

Answer 26

Regular.
With finite stack… we can make Finite Automata of a language. We need infinite stack to go from Regular -> CFL

Question 27

If a language satisfies the pumping Lemma for CFL then Language is CFL.
T or F ?

Answer 27

False.
By pumping lemma we can never say that a language is regular or cfg .it can only be used to prove that a certain langusge is not reg or not cfg.

Question 28

A context-free grammar is ambiguous if…

Answer 28

1) it produces more than one parse tree for some sentence.
or
2) It produces more that one leftmost derivation for some sentence
or
3) It produces more than one rightmost derivation for some sentence.

Question 29

A context free language is called ambiguous if…

Answer 29

there is no unambiguous grammar to define that language and it is also called inherently ambiguous Context Free Languages.

Question 30

Deterministic CFL are always unambiguous.
T or F ?

Answer 30

TRUE

Question 31

There exist an algorithm to convert ambiguous CFG to unambiguous CFG.
T or F?

Answer 31

FALSE.
There is no algorithm to convert ambiguous CFG to unambiguous CFG.

Question 32

If a context free grammar G is ambiguous, language generated by grammar L(G) will always be ambiguous.
T or F?

Answer 32

FALSE
If a context free grammar G is ambiguous, language generated by grammar L(G) may or may not be ambiguous

Question 33

There exist context-free languages such that all the context-free grammars generating them are ambiguous.
T or F?

Answer 33

TRUE
is correct because for ambiguous CFL’s, all CFG corresponding to it are ambiguous.

Question 34

An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it.
T or F?

Answer 34

TRUE
is also correct as unambiguous CFG has a unique parse tree for each string of the language generated by it.

Question 35

A finite set of string from one alphabet is always a regular language.
T or F?

Answer 35

TRUE
is also true as finite set of string is always regular.

Question 36

Both deterministic and non-deterministic pushdown automata always accept the same set of languages.
T or F

Answer 36

FALSE
is false as some languages are accepted by Non- deterministic PDA but not by deterministic PDA.

Question 37

Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
T or F ?