Context Free Language and Push Down Automata Flashcards
P is Regular and Q is Context Free.
P ^ Q is Regular?
No. P ^ Q is not regular
P is Regular and Q is Context Free.
P - Q is Regular?
No. P - Q is not regular
P is Regular and Q is Context Free.
P Compliment is Regular?
Yes. Complement of any regular language is regular.
P is Regular and Q is Context Free.
Q Compliment is Regular?
NO. Context Free Languages are not closed under Compliment.
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’
CFL and REG both are closed under UNION
(T or F)?
TRUE
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.
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.
CFL and REG both are closed under CONCATENATION
(T or F)?
TRUE
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.
What is Type - 0 Grammar?
Recursively Enumerable.
Automata = Turing Machine.
What is Type - 1 Grammar?
Context Sensitive
Automata = Linear-bounded non-deterministic machine.
What is Type - 2 Grammar?
Context Free
Automata = Non-deterministic push down automata
What is Type - 3 Grammar?
Regular
Automata = Finite state automata
What is the set order of Grammar?
i.e. A < B < C < D
REG < CFL < CSL < RE
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 ?
