## Convert PDA to CFG – Language of Palindromes over $\{a,b\}^+$

I tried to convert the following PDA $$M$$

to a CFG and got the following results. However I’m not quite sure if I did the algorithm the right way. I feel like I maybe misunderstood some the algorithm when it comes to the $$A_{p,q} \to xA_{r,s}y$$ part. Could you help me to clear things up?

$$G = (V,\Sigma,P,S)$$ with \begin{align*} V = \{&A_{0,0},A_{0,1},A_{0,2},A_{0,3},A_{0,4},A_{1,0},A_{1,1},A_{1,2},A_{1,3},A_{1,4},A_{2,0},A_{2,1},A_{2,2},A_{2,3},A_{2,4},\ &A_{3,0},A_{3,1},A_{3,2},A_{3,3},A_{3,4},A_{4,0},A_{4,1},A_{4,2},A_{4,3},A_{4,4},S\}, \end{align*} $$\Sigma = \{a,b\}$$, $$S = A_{0,4}$$ and the following productions: \begin{align*} S &\to A_{0,4}\ A_{0,0} &\to \epsilon\ A_{1,1} &\to \epsilon\ A_{2,2} &\to \epsilon\ A_{3,3} &\to \epsilon\ A_{4,4} &\to \epsilon\ A_{0,0} &\to A_{0,0}A_{0,0} \vert A_{0,1} A_{1,0} \vert A_{0,2}A_{2,0} \vert A_{0,3}A_{3,0} \vert A_{0,4}A_{4,0}\ A_{0,1} &\to A_{0,0}A_{0,1} \vert A_{0,1} A_{1,1} \vert A_{0,2}A_{2,1} \vert A_{0,3}A_{3,1} \vert A_{0,4}A_{4,1}\ A_{0,2} &\to A_{0,0}A_{0,2} \vert A_{0,1} A_{1,2} \vert A_{0,2}A_{2,2} \vert A_{0,3}A_{3,2} \vert A_{0,4}A_{4,2}\ &\vdots\ A_{4,4} &\to A_{4,0}A_{0,4} \vert A_{4,1} A_{1,4} \vert A_{4,2}A_{2,4} \vert A_{4,3}A_{3,4} \vert A_{4,4}A_{4,4}\ A_{0,4} &\to A_{1,3}\ A_{1,3} &\to aA_{1,3}a\ A_{1,3} &\to bA_{1,3}b\ A_{1,3} &\to aA_{1,1}\ A_{1,3} &\to bA_{1,1} \end{align*}

## Build a CFG for w#x where w, x ∈ {0, 1}, |w| = |x|, w and x are not palindromes

Can someone help me solve this CFL?

$$L = \{w\#x | w, x \in \{0, 1\}^*, (|w| = |x|), (w \neq x^R) \}$$

## palindromes with integers by adding numbers until a palindrome is reached- java

I’m not necessarily trying to ask for code but I’m not sure where I’m going wrong with this or why my current code is printing 10. Can someone help me understand where I’m going wrong.

 public static int palindroCount(int n){     String pal=n+"";     String lap="";     int count=-1;     for (int i=pal.length()-1; i>0; i--){         lap+=pal.substring(i,i+1);     }     if (pal.equals(lap)) {         count = 0;     } else {         while ((!pal.equals(lap)) && count<10){             pal=n*2+"";             for (int i=pal.length()-1; i>0; i--){                 lap+=pal.substring(i,i+1);             }             count++;         }     }     return count;     //This is wrong and I have no idea on how to get it. It prints out 10,      //when it's supposed to print 2 }  public static void main(String[] args) {     test2Prep model= new test2Prep();     System.out.println(model.palindroCount(159)); } 

The question in the textbook is: Given a positive integer n, return the number of p-additions needed to make it a palindrome. A p-addition is the addition of the number to its inverse. Ex, if n=159, the first p-addition yields: 159+951=1110. The second p-addition yields: 1110+ 0111=1221, which is a palindrome, so the return is 2. if n is a palindrome to begin with return 0, and if the number doesn’t become a palindrome after 10 p-additions then return -1.

## First half of context-free palindromes

If $$L\subseteq\Sigma^*$$ is a regular language, then $$\text{mir}(L) = \{ww^R \mid w\in L\}$$ is context-free. This is a nice exercise.

Question: does the reverse hold? Thus, if $$\text{mir}(L)$$ is context-free, do we always have $$L$$ is regular?

## Why is this pushdown automata for some palindromes right?

$$B = \{w \in \{0,1\}^* | w^R = w, w \text{ length is odd} \}$$

Solution:

For example: $$111$$ should be accepted

steps are

$$q_1 \to q_2$$ stack: []

$$q_2 \to q_2$$ stack: $$[ , 1, 1]$$ (using up $$11$$ only having a single $$1$$ left)

$$q_2 \to q_3$$ stack: $$[ , 1, 1]$$ (no change except we lost our final $$1$$)

$$q_3 \to$$ (no strings left to use)

I’m confused understanding this

## Minimum number of deleting palindromes to delete whole string

Let’s say we have given array $$A$$ of size $$n$$. Our goal is to delete the whole array with minimum steps. In one step we can choose substring (consecutive elements from the string) and delete it only if it is a palindrome (if we can read it in the same way from the front and the back).

For example the array 1 1 5 9 5 1 can be deleted in two steps. Step 1: Delete substring 5, 9, 5. Then delete the remaining substring 1, 1, 1. We only need to return 2, the number of steps.

My idea is to use dynamic programming technique. Our state would be $$DP[L][R]$$ meaning the minimum number of steps to delete the substring in range $$[L, R]$$. However I can’t really work the transitions, since there can be cases when our front element will merge with some element in the middle and with some elements in the back, so I don’t know how to cover all transitions between different states.

## Find palindromes in circular rotated string

I’m trying to tackle a programming challenge to determine how many palindromes exist in a given string that is being rotated character by character. My solution works, but it’s too slow, and I’m struggling on where to optimize it.

For example, the string “cacbbba” would rotate 6 times, and would have 3 palindromes in each string.

1. cacbbba (3 palindromes)
2. acbbbac (3 palindromes)
3. cbbbaca (3 palindromes)
4. bbbacac (3 palindromes)
5. bbacacb (3 palindromes)
6. bacacbb (3 palindromes)
7. acacbbb (3 palindromes)
function circularPalindromes(s) {     const k = s.length;     const result = [];     const isPalindrome = (str) => {         const len = str.length;          for (let i = 0; i < len / 2; i++) {             if (str[i] !== str[len - 1 - i]) {                 return false;             }         }          return true;     };     const subs = (s) => {         let max = 0;          for (let i = 0; i < s.length; i++) {             for (let j = 1; j <= s.length - i; j++) {                 const sub = s.substring(i, i + j);                  if (sub.length < 2) continue;                  if (isPalindrome(sub) && sub.length > max) {                     max = sub.length;                 }             }         }          return max;     };      for (let i = 0; i < k; i++) {         result.push(subs(s.substring(i, k) + s.substring(0, i)));     }      return result; } console.log(circularPalindromes('cacbbba'));