Question

Any language that can be recognized by a pushdown automaton (PDA) can also be described by...

Any language that can be recognized by a pushdown automaton (PDA) can also be described by a regular expression.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

No,

because regualar expression is the form of regualr language having finite state.there are many languages which can not accepted by regular languages but it can be accepted by PDA because with the help of stack,it makes much powerful than regualr lanugae to accept any language.

Ex - anbn : n>=1 it is CFL which can be accepted by pda by comparing number of a's and that number should be equal to number of b's but in the case of regular language,it has finite memory to accept..

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Give an pushdown automaton (PDA) that will accept the following language: {w ∈ {a, b}∗ |...
Give an pushdown automaton (PDA) that will accept the following language: {w ∈ {a, b}∗ | w has twice as many bs as as}.
Question 2 a) Construct a Pushdown Automaton (PDA) for the language L (M) = {a, b}*...
Question 2 a) Construct a Pushdown Automaton (PDA) for the language L (M) = {a, b}* where, if there are any a’s must precede all b's and the number of b's must be equal to or twice the number of a’s. a) Trace the computations for the strings aabb, bbb, and abb in the PDA obtained in Question 2
Draw state diagrams of pushdown automaton (PDA) for below languages : L1 = {w | w...
Draw state diagrams of pushdown automaton (PDA) for below languages : L1 = {w | w ∈ {a,+,-,*,/,(,)} *, w is a legal arithmetic expression in infix form} L5 = {w | w ∈ {0,1}*, w is a palindrome} L6 = {w | w ∈ {0,1}*, w contains equal numbers of 0s and 1s} Give CFG(Context free grammar) for the language L1 = {w | w ∈ {a,+,-,*,/,(,)} *, w is a legal arithmetic expression in infix form}
The language described by the regular expression ((ab)* (c|d))*
The language described by the regular expression ((ab)* (c|d))*
1. Consider the deterministic finite automaton (K, Σ, δ, s, F) where K = {p, q,...
1. Consider the deterministic finite automaton (K, Σ, δ, s, F) where K = {p, q, r}, Σ = {a, b, c}, s = p, F = {q} and δ is given by the following chart: x       y     δ(x, y) p       a         q p       b         q p       c          r q       a         r q       b         p q       c         p r        a          r r        b          r r        c           r Find a regular expression for the language recognized by this automaton
Use CFG or PDA to prove L= {0a1b0c : b ≠ a + c; a, b,...
Use CFG or PDA to prove L= {0a1b0c : b ≠ a + c; a, b, c ≥ _0} is a context-free language. Please add your explanation, thank you. If you can use the theorem(union of CFL and regular language = CFL) is also welcomed.
1.2 Which of the following statements is wrong?        a). A set is a subset of itself...
1.2 Which of the following statements is wrong?        a). A set is a subset of itself        b). Emptyset is a subset of any set        c). A set is a subset of its powerset        d). The cardinality of emptyset is 0 1.3. Which of the following statements is correct?        a). A string is a set of symbols from an alphabet        b). The length of the concatenation of two strings can           be the same as one of them        c). The length of...
prove that any regular language L can be represented by a regular expression in DNF(a1Ua2U...Uan), where...
prove that any regular language L can be represented by a regular expression in DNF(a1Ua2U...Uan), where none of ai, 1<=i<=n, contains the operator U.
Given that it cannot be described by a function, how can a looping curve (or any...
Given that it cannot be described by a function, how can a looping curve (or any curve that fails the vertical line test) be described mathematically? Simple legible and 2 sentences please.
2. The Cantor set C can also be described in terms of ternary expansions. (a.) Prove...
2. The Cantor set C can also be described in terms of ternary expansions. (a.) Prove that F : C → [0, 1] is surjective, that is, for every y ∈ [0, 1] there exists x ∈ C such that F(x) = y.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT