Design a PDA of all strings of 0's and 1's that are not of the form ww^R
I have to create a PDA(pushdown automata) that accepts strings that not of the form .
For example it accepts 0011, 1100, 11000 but not accepts 1001, 011110, 0110.
How can I create this PDA? I know the answer of not accepting ww, but can't get an insight to make this one.
I would appreciate if you let me know the answer or nice hint to make it.
To accept ww^R, you push the symbols of w onto the stack, nondeterministically guess that you have reached the end of w, and then read w^R while popping matching symbols off the stack. The only way this can possibly accept is if your guess was right, and then it will only accept if your string is of the correct form.
To accept everything not of the form ww^R, consider the following:
First, nondeterministically guess about the parity of the input's length. If you guess that that the input has odd length, and you are right, then it is a string in the language since an odd-length string cannot be of the form ww^R. Doing this allows us to focus the other branch on the case of even-length strings not of the required form.
The defining characteristic of even-length strings not of the form ww^R is that for at least one index k from 1 to |w|, it is true that x[k] is not equal to x[2|w|-k+1]. So, we can push w onto the stack, just as a PDA for ww^R would; and we can nondeterministically guess that we have reached the end of w in the same way. However, instead of requiring the input symbols be equal to the top-of-stack symbols, we will pop a stack symbol for any input symbol, and we will further require that at least one of the input symbols does not match its corresponding top-of-stack symbol. We can do this by having two states for the popping phase: the first corresponding to not having encountered at least one mismatch, and the second corresponding to having seen one or more mismatches. Finally, we can accept if we are in the second of these states with no further input symbols and an empty stack.
- Create a DFA that contains "11" or ends with "10"
- How to detect programmatically if two Globs intersect or not in Node.js?
- How can a programming language that is specified using a context-free grammar, be capable of expressing a Turing Machine?
- How can I construct a grammar that generates this language?
- Regular Expression: Language of all those strings which do not contain substring 'bb'
- Find a finite automata that for the language L={0,1,2} | needs to include 1002 1,2 are odd and 0 is even
- How to escape stable pattern in conway's game of life?
- Designing a Turing Machine's state table
- Whether this is the general approach for making a DFA for accepting prefix language of a given regular language?
- Regular Expression for Automata for Strings that do not end in 01
- Evaluating Polish Notation in Java with 2 stacks
- DFA- Set of all strings whose 10th symbol from the right end is 1
- NFA or DFA accepting # of positions of 4k between 0's
- Clarification on Regular Language pumping lemma
- Writing the production rules of this finite state machine
- what is the meaning of {} in the regular expressions {a + ab}*
- What is the difference between (a+b)* and (a*b*)*?
- Prove that if ϵ ∈ L1 then L2 ⊆ L2 • L1
- The set of all strings over {0,1} that do not contain both the sequence “101” and the sequence “010”
- Design DFA accepting decimal strings divisible by 7
- Difference between transition diagram and finite automata
- Deterministic Pushdown automa vs Non-deterministic pushdown Automata
- Does a language compiler use a complex DFA to accept programs?
- Complement of non-deterministic context-free language
- Can I use stack in Turing Machine?
- Convert regular expression to CFG
- Using regular expressions check if a particular segment exist in a given string
- How to work with weighted automata dataset for Keras Regression
- Plotting Automata Grid Iterations in R
- Design a PDA of all strings of 0's and 1's that are not of the form ww^R