Whether the PDA accepts all the languages that have been accepted by the FA? give example
Answers
Answer:Day Date Contents Slides Assignments
1 Sep 27 Regular Language- alphabets, language(set of strings), language class or language family
All languages -uncountably infinte, set of all languages(Finite, Regular, Context free) are countably infinite, there is an uncountable recursive set of languages outside recursively enumerable languages
Finite Automata- Deterministic Automata and Non Deterministic Automata- mathematical representation
Number of DFA's possible with two states over {0,1}
What do you know about Regular language?
1.) Finite automata acceptance
2.) Deterministic finite automata acceptance
3.) Has an equivalent regular expression
Operators in regular expression, Deterministic and Non Deterministic languages are not same in CFL
Pumping Lemma- used to check if a language is not regular
Regular set --> Pumping lemma
Definition with examples
Methods to check if a language is regular:
(i) Pumping lemma- one way (ii) Regular expression/ Finite automata/ Regular grammar- two way (iii) Myhill- Nerode theorem- equivalence relation for this theorem, distinguishing string
Difference between context-sensitive and recursive language- space complexity is linear in LBA, find an example for language accepted by TM but not LBA
2 Sep 28 Product automata
If L is regular:
Is L empty?
Is L equal to sigma*?
Is reverse of L regular?
Is first half(L) regular?
More examples to check whether grammar is regular or not.
Regular Grammar: G=(V, T, P, S)
Left linear grammar- only one non-terminal on left of each production
Right linear grammar- only one non-terminal on right of each production
All linear grammars are not regular, but all regular languages are either left linear or right linear.
Context Free Grammar- Pushdown Automata = NFA + Stack
L={a^n c b^n | n >= 0} not regular
Push all a's into stack, if c is reached do not do anything on stack, now for each b pop an a from stack. If stack is empty finally then string is accepted if the input is over.
PDA- mathematical representation, accepts all regular languages
Acceptance by final state and acceptance by empty stack- both are eqivalent in case of PDA
In Deterministic PDA acceptance by empty stack is a subset of acceptance by final state.
3 Sep 29 Half(L) is regular - how to construct DFA for Half(L)
Squareroot(L) is regular
Square(L) is not regular
4 Sep 30-Oct 2 Solve GO pdf questions on regular language,regular expressions and context free languages
5 Oct 3 Pushdown Automata
Given a PDA which accepts by empty stack, how to convert it to PDA accepts by final state.
{aab,aa,a} - Can you make PDA that accept by empty stack?
NFA = DFA < DPDA < PDA
PDA by empty stack = PDA by final state
DPDA by empty stack < DPDA by final state
{a,aa,aab}- If strings are prefixes then it cannot be accepted by DPDA by empty stack.
Which is more powerful? DFA or DPDA by empty stack
These two are not comparable. There are some languages by DPDA empty stack which cannot be accepted by DFA and vice-versa.
Language of [DPDA by empty stack] = LR(0)
Assignment: Take an input executable and an input 'w' for that and outputs "yes" when the executable finish running.
Explanation:hope this helps u plz mark me as the brainliest
Explanation:
Yes.
A pushdown automaton (PDA) is a limited state apparatus which has supplementary stack accommodation. The developments a device makes are based not only on the information and contemporary state but also on the mound. Specifically, from the source state with an abandoned stack, we
formulate the undivided string,
close in a terminal state
close with an empty stack.
The language admitted by a PDA M, L(M), is the collection of all admitted strings. The hollow stack is our fundamental new provision corresponding to calculable state machines. The standards that we commonly have very few states; in common, there is so much more authority from functioning the stack representation.