Context Free Language and Push Down Automata Flashcards by Vansil Chauhan

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

No. P ^ Q is not regular

How well did you know this?

Not at all

Perfectly

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

No. P - Q is not regular

How well did you know this?

Not at all

Perfectly

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

Yes. Complement of any regular language is regular.

How well did you know this?

Not at all

Perfectly

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

NO. Context Free Languages are not closed under Compliment.

How well did you know this?

Not at all

Perfectly

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

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

How well did you know this?

Not at all

Perfectly

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

TRUE

How well did you know this?

Not at all

Perfectly

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

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.

How well did you know this?

Not at all

Perfectly

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

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.

How well did you know this?

Not at all

Perfectly

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

TRUE

How well did you know this?

Not at all

Perfectly

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

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

How well did you know this?

Not at all

Perfectly

What is Type - 0 Grammar?

Recursively Enumerable.
Automata = Turing Machine.

How well did you know this?

Not at all

Perfectly

What is Type - 1 Grammar?

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

How well did you know this?

Not at all

Perfectly

What is Type - 2 Grammar?

Context Free
Automata = Non-deterministic push down automata

How well did you know this?

Not at all

Perfectly

What is Type - 3 Grammar?

Regular
Automata = Finite state automata

How well did you know this?

Not at all

Perfectly

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

REG < CFL < CSL < RE

How well did you know this?

Not at all

Perfectly

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

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

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

TRUE

DCFL Union Regular is DCFL.
T or F

TRUE

DCFL is closed under which operations?

COMPLEMENT
INVERSE HOMOMORPHISM
INTERSECTION with REG

REG = Regular Language, DCFL = Deterministic Context Free Language

REG is closed under which operations?

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

REG = Regular Language

RE is not closed under which operations?

COMPLEMENT.

RE = Recursively Enumerable Language

CFL is not closed under which operations?

INTERSECTION,
COMPLEMENT.

CFL = Context Free Language

REC is closed under which operation?

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

REC = Recursive Language

CSL is closed under which operation?

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

CLS = Context Sensitive Language

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

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

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

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

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

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.

A context-free grammar is ambiguous if...

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.

A context free language is called ambiguous if...

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

Deterministic CFL are always unambiguous. T or F ?

TRUE

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

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

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

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

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

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

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

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

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

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

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

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

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