Ich habe auch ein wenig Code dazu geschrieben.
Die beiden Sprachen sind nicht äquivalent.
Die Bedingung oben i + k = j + l wird aber von beiden Sprachen eingehalten.
Den Unterschied, den ich gefunden habe, findet man im Code.
Eventuell gibt es noch mehr Unterschiede oder man kann den Unterschied anders formulieren:
[CODE lang="java" title="AbstractCartesianProductIterator"]import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
abstract public class AbstractCartesianProductIterator<RESULT, LEFT, RIGHT>
implements Iterator<RESULT>
{
private final Iterator<LEFT> leftIterator;
private boolean hasLeft;
private LEFT currentLeft;
private final Iterable<RIGHT> rightIterable;
private Iterator<RIGHT> rightIterator;
/**
* Constructor.
*
* @param leftIterator
* @param rightIterable
*/
public AbstractCartesianProductIterator(
final Iterator<LEFT> leftIterator ,
final Iterable<RIGHT> rightIterable )
{
this.leftIterator = Objects.requireNonNull( leftIterator );
this.rightIterable = Objects.requireNonNull( rightIterable );
if ( this.leftIterator.hasNext() )
{
this.hasLeft = true;
this.currentLeft = leftIterator.next();
this.rightIterator = Objects.requireNonNull( rightIterable.iterator() );
}
}
/**
* Constructor.
*
* @param leftIterable
* @param rightIterable
*/
public AbstractCartesianProductIterator(
final Iterable<LEFT> leftIterable ,
final Iterable<RIGHT> rightIterable )
{
this(
leftIterable.iterator() ,
rightIterable );
}
/**
* Method to implement to combine two elements of the left and the right source.
* @param left element from the left source
* @param right element from the right source
* @return result of combination of the given elements
*/
abstract RESULT combine(
final LEFT left ,
final RIGHT right );
@Override
final public boolean hasNext()
{
return
this.hasLeft &&
this.rightIterator.hasNext();
}
@Override
final public RESULT next()
{
if ( ! hasNext() )
{
throw new NoSuchElementException();
}
final RIGHT right = this.rightIterator.next();
final RESULT result =
combine(
this.currentLeft ,
right );
if ( ! this.rightIterator.hasNext() )
{
if ( this.leftIterator.hasNext() )
{
this.currentLeft = this.leftIterator.next();
this.rightIterator = Objects.requireNonNull( this.rightIterable.iterator() );
}
else
{
this.hasLeft = false;
this.currentLeft = null; // free memory
}
}
return result;
}
}
[/CODE]
[CODE lang="java" title="ConcatIterator"]import java.util.Iterator;
import java.util.Objects;
/**
* Concatenation of two {@link Iterator}.
*/
public class ConcatIterator<E>
implements Iterator<E>
{
private final Iterator<E> first;
private final Iterator<E> second;
/**
* Constructor.
*
* @param first
* @param second
*/
public ConcatIterator(
final Iterator<E> first ,
final Iterator<E> second )
{
this.first = Objects.requireNonNull( first );
this.second = Objects.requireNonNull( second );
}
@Override
public boolean hasNext()
{
return
this.first.hasNext() ||
this.second.hasNext();
}
@Override
public E next()
{
if ( this.first.hasNext() )
{
return this.first.next();
}
return this.second.next();
}
}
[/CODE]
[CODE lang="java" title="ConcatIteratorWithIterable"]import java.util.Iterator;
import java.util.Objects;
public class ConcatIteratorWithIterable<E>
implements Iterator<E>
{
private final Iterator<E> firstIterator;
private final Iterable<E> secondIterable;
private Iterator<E> secondIterator;
/**
* Constructor.
*
* @param firstIterator
* @param secondIterable
*/
public ConcatIteratorWithIterable(
final Iterator<E> firstIterator ,
final Iterable<E> secondIterable )
{
this.firstIterator = Objects.requireNonNull( firstIterator );
this.secondIterable = Objects.requireNonNull( secondIterable );
}
/**
* Constructor.
*
* @param firstIterable
* @param secondIterable
*/
public ConcatIteratorWithIterable(
final Iterable<E> firstIterable ,
final Iterable<E> secondIterable )
{
this(
firstIterable.iterator() ,
secondIterable );
}
@Override
public boolean hasNext()
{
return
this.firstIterator.hasNext() ||
( this.secondIterator != null && this.secondIterator.hasNext() );
}
@Override
public E next()
{
if ( this.firstIterator.hasNext() )
{
final E next = this.firstIterator.next();
if ( ! this.firstIterator.hasNext() )
{
this.secondIterator = Objects.requireNonNull( this.secondIterable.iterator() );
}
return next;
}
return this.secondIterator.next();
}
}
[/CODE]
[CODE lang="java" title="Pair"]
public final class Pair<LEFT, RIGHT>
{
public final LEFT left;
public final RIGHT right;
/**
* Constructor.
*
* @param left
* @param right
*/
public Pair(
final LEFT left ,
final RIGHT right )
{
this.left = left;
this.right = right;
}
@Override
public String toString()
{
return "[" + this.left + ", " + this.right + "]";
}
}
[/CODE]
[CODE lang="java" title="LimitIterator"]import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
public class LimitIterator<E>
implements Iterator<E>
{
public final int limit;
private final Iterator<E> iteratorToLimit;
private int count;
/**
* Constructor.
*
* @param iteratorToLimit
* @param limit
*/
public LimitIterator(
final Iterator<E> iteratorToLimit ,
final int limit )
{
this.iteratorToLimit = Objects.requireNonNull( iteratorToLimit );
this.limit = limit;
}
@Override
public boolean hasNext()
{
return
( this.count < this.limit ) &&
this.iteratorToLimit.hasNext();
}
@Override
public E next()
{
if ( ! hasNext() )
{
throw new NoSuchElementException();
}
this.count++;
return this.iteratorToLimit.next();
}
}
[/CODE]
[CODE lang="java" title="LimitIterable"]import java.util.Iterator;
import java.util.Objects;
public class LimitIterable<E>
implements Iterable<E>
{
public final int limit;
private final Iterable<E> iterableToLimit;
/**
* Constructor.
*
* @param iterableToLimit
* @param limit
*/
public LimitIterable(
final Iterable<E> iterableToLimit ,
final int limit )
{
this.iterableToLimit = Objects.requireNonNull( iterableToLimit );
this.limit = limit;
}
@Override
public Iterator<E> iterator()
{
return new LimitIterator<>(
// iteratorToLimit
this.iterableToLimit.iterator() ,
this.limit );
}
}
[/CODE]
[CODE lang="java" title="StringWrapFromZeroToCountIterator"]import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
public class StringWrapFromZeroToCountIterator
implements Iterator<String>
{
public final int wrapCount;
public final String leftWrapStr;
public final String rightWrapStr;
private final Iterator<String> iteratorToWrap;
private int currentWrapCount;
private boolean hasNextStr = false;
private String nextStr;
/**
* Constructor.
*
* @param iteratorToWrap
* @param leftWrapStr
* @param rightWrapStr
* @param wrapCount
*/
public StringWrapFromZeroToCountIterator(
final Iterator<String> iteratorToWrap ,
final String leftWrapStr ,
final String rightWrapStr ,
final int wrapCount )
{
this.iteratorToWrap = Objects.requireNonNull( iteratorToWrap );
this.leftWrapStr = leftWrapStr;
this.rightWrapStr = rightWrapStr;
this.wrapCount = wrapCount;
if ( this.iteratorToWrap.hasNext() )
{
nextStr = this.iteratorToWrap.next();
currentWrapCount = 0;
hasNextStr = true;
}
}
@Override
public boolean hasNext()
{
return hasNextStr;
}
@Override
public String next()
{
if ( ! hasNext() )
{
throw new NoSuchElementException();
}
final String result = nextStr;
skip();
return result;
}
private void skip()
{
if ( this.currentWrapCount < this.wrapCount )
{
this.nextStr =
this.leftWrapStr +
"" + // avoid NullPointerException
this.nextStr +
this.rightWrapStr;
this.currentWrapCount++;
}
else if ( this.iteratorToWrap.hasNext() )
{
nextStr = this.iteratorToWrap.next();
currentWrapCount = 0;
}
else
{
hasNextStr = false;
}
}
}
[/CODE]
[CODE lang="java" title="AbstractCartesianProductIteratorTest"]import static org.junit.Assert.*;
import java.util.Arrays;
import org.junit.Assert;
import org.junit.Ignore;
import org.junit.Test;
/**
* JUnit4 test.
*/
public class AbstractCartesianProductIteratorTest
{
/**
* Test method for {@link AbstractCartesianProductIterator#AbstractCartesianProductIterator(java.util.Iterator, java.lang.Iterable)}.
*/
@Ignore
@Test
public void testAbstractCartesianProductIteratorIteratorOfLEFTIterableOfRIGHT() {
fail("Not yet implemented");
}
/**
* Test method for {@link AbstractCartesianProductIterator#AbstractCartesianProductIterator(java.lang.Iterable, java.lang.Iterable)}.
*/
@Ignore
@Test
public void testAbstractCartesianProductIteratorIterableOfLEFTIterableOfRIGHT() {
fail("Not yet implemented");
}
/**
* Test method for {@link AbstractCartesianProductIterator#combine(java.lang.Object, java.lang.Object)}.
*/
@Test
public void testCombine()
{
final Iterable<String> leftIterable =
Arrays.asList(
"a" ,
"b" ,
"c" );
final Iterable<Integer> rightIterable =
Arrays.asList(
0 ,
1 ,
2 );
final AbstractCartesianProductIterator<String, String, Integer> cartesianProductIterator =
new AbstractCartesianProductIterator<String, String, Integer>(
leftIterable ,
rightIterable )
{
@Override
String combine(
final String left ,
final Integer right )
{
return left + right;
}
};
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"a0" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"a1" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"a2" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"b0" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"b1" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"b2" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"c0" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"c1" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"c2" ,
//actual
cartesianProductIterator.next() );
Assert.assertFalse( cartesianProductIterator.hasNext() );
}
/**
* Test method for {@link AbstractCartesianProductIterator#hasNext()}.
*/
@Ignore
@Test
public void testHasNext() {
fail("Not yet implemented");
}
/**
* Test method for {@link AbstractCartesianProductIterator#next()}.
*/
@Ignore
@Test
public void testNext() {
fail("Not yet implemented");
}
}
[/CODE]
[CODE lang="java" title="StringWrapFromZeroToCountIteratorTest"]import static org.junit.Assert.fail;
import java.util.Arrays;
import org.junit.Assert;
import org.junit.Ignore;
import org.junit.Test;
/**
* JUnit4 test.
*/
public class StringWrapFromZeroToCountIteratorTest
{
@Ignore
@Test
public void testStringWrapFromZeroToCountIterator() {
fail("Not yet implemented");
}
@Ignore
@Test
public void testHasNext() {
fail("Not yet implemented");
}
@Ignore
@Test
public void testNext()
{
fail("Not yet implemented");
}
@Test
public void test()
{
final StringWrapFromZeroToCountIterator wrapIterator =
new StringWrapFromZeroToCountIterator(
//iteratorToWrap
Arrays.asList( "1" , "2" ).iterator() ,
//leftWrapStr
"a" ,
//rightWrapStr
"b" ,
//wrapCount
2 );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"1" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"a1b" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"aa1bb" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"2" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"a2b" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"aa2bb" ,
//actual
wrapIterator.next() );
Assert.assertFalse( wrapIterator.hasNext() );
}
}
[/CODE]
[CODE lang="java" title="GenerateWords"]import java.util.Arrays;
import java.util.Iterator;
/*
https://www.java-forum.org/thema/beweisen-dass-eine-grammatik-eine-sprache-erzeugt.192150/#post-1254785
Sei G = ( {S, A, B, C}, {a, b, c, d}, P, S) mit {
S -> aSd,
S -> ABC,
A -> aAb,
B -> bBc,
C -> cCd,
A -> empty,
B -> empty
C -> empty}
a) Zeigen Sie L(G) = {a_hoch_i b_hoch_j c_hoch_k d_hoch_l | i + k = j + l}.
b) Wie lautet L(G) wenn die erste Produktionsregel weggelassen wird?
*/
/*
Sprache a)
i (count of a) := count of not_empty S + count of not_empty A
j (count of b) := count of not_empty A + count of not_empty B
k (count of c) := count of not_empty B + count of not_empty C
l (count of d) := count of not_empty C + count of not_empty S
Sprache b)
i (count of a) := count of not_empty A
j (count of b) := count of not_empty A + count of not_empty B
k (count of c) := count of not_empty B + count of not_empty C
l (count of d) := count of not_empty C
*/
public class GenerateWords
{
static final int LIMIT = 4;
// A -> aBb
static class A_Iterator_without_empty
extends AbstractCartesianProductIterator<String, Pair<String, String>, String>
{
/**
* Constructor.
*/
public A_Iterator_without_empty()
{
super(
//leftIterable
Arrays.asList( new Pair<>( "a" , "b" ) ) ,
//rightIterable
() -> new A_Iterator() );
}
@Override
String combine(
final Pair<String, String> left ,
final String right )
{
return left.left + right + left.right;
}
}
// A -> empty, A -> aBb
static class A_Iterator
extends ConcatIteratorWithIterable<String>
{
/**
* Constructor.
*/
public A_Iterator()
{
super(
//firstIterable
Arrays.asList( "" ) , // empty
//secondIterable
() -> new A_Iterator_without_empty() );
}
}
// B -> bBc
static class B_Iterator_without_empty
extends AbstractCartesianProductIterator<String, Pair<String, String>, String>
{
/**
* Constructor.
*/
public B_Iterator_without_empty()
{
super(
//leftIterable
Arrays.asList( new Pair<>( "b" , "c" ) ) ,
//rightIterable
() -> new B_Iterator() );
}
@Override
String combine(
final Pair<String, String> left ,
final String right )
{
return left.left + right + left.right;
}
}
// B -> empty, B -> bBc
static class B_Iterator
extends ConcatIteratorWithIterable<String>
{
/**
* Constructor.
*/
public B_Iterator()
{
super(
//firstIterable
Arrays.asList( "" ) , // empty
//secondIterable
() -> new B_Iterator_without_empty() );
}
}
// C -> cCd
static class C_Iterator_without_empty
extends AbstractCartesianProductIterator<String, Pair<String, String>, String>
{
/**
* Constructor.
*/
public C_Iterator_without_empty()
{
super(
//leftIterable
Arrays.asList( new Pair<>( "c" , "d" ) ) ,
//rightIterable
() -> new C_Iterator() );
}
@Override
String combine(
final Pair<String, String> left ,
final String right )
{
return left.left + right + left.right;
}
}
// C -> empty, C -> cCd
static class C_Iterator
extends ConcatIteratorWithIterable<String>
{
/**
* Constructor.
*/
public C_Iterator()
{
super(
//firstIterable
Arrays.asList( "" ) , // empty
//secondIterable
() -> new C_Iterator_without_empty() );
}
}
// BC
static class BC_Iterator
extends AbstractCartesianProductIterator<String, String, String>
{
public BC_Iterator()
{
super(
//leftIterable
new LimitIterable<>( () -> new B_Iterator() , LIMIT ) ,
//rightIterable
new LimitIterable<>( () -> new C_Iterator() , LIMIT ) );
}
@Override
String combine(
final String left ,
final String right )
{
return left + right;
}
}
// S -> ABC
static class ABC_Iterator
extends AbstractCartesianProductIterator<String, String, String>
{
public ABC_Iterator()
{
super(
//leftIterable
new LimitIterable<>( () -> new A_Iterator() , LIMIT ) ,
//rightIterable
() -> new BC_Iterator() );
}
@Override
String combine(
final String left ,
final String right )
{
return left + right;
}
}
// S -> aSd
//static class S_recursive_Iterator
//extends AbstractCartesianProductIterator<String, Pair<String, String>, String>
//{
// /**
// * Constructor.
// */
// public S_recursive_Iterator()
// {
// super(
// //leftIterable
// Arrays.asList( new Pair<>( "a" , "d" ) ) ,
// //rightIterable
// new LimitIterable<>( () -> new S_recursive_Iterator() , LIMIT ) );
// }
//
// @Override
// String combine(
// final Pair<String, String> left ,
// final String right )
// {
// return left.left + right + left.right;
// }
//}
static class S_Iterator
extends StringWrapFromZeroToCountIterator
{
/**
* Constructor.
*/
public S_Iterator()
{
super(
//iteratorToWrap
new ABC_Iterator() ,
//leftWrapStr
"a" ,
//rightWrapStr
"d" ,
//wrapCount
LIMIT );
}
}
public static void main(String[] args)
{
System.out.println( "A:" );
final Iterable<String> a_Iterable = new LimitIterable<>( () -> new A_Iterator() , LIMIT );
System.out.println( size( a_Iterable ) );
for ( final String aStr : a_Iterable )
{
System.out.println( aStr );
}
System.out.println( "============================================================================================" );
System.out.println( "B:" );
final Iterable<String> b_Iterable = new LimitIterable<>( () -> new B_Iterator() , LIMIT );
System.out.println( size( b_Iterable ) );
for ( final String bStr : b_Iterable )
{
System.out.println( bStr );
}
System.out.println( "============================================================================================" );
System.out.println( "C:" );
final Iterable<String> c_Iterable = new LimitIterable<>( () -> new C_Iterator() , LIMIT );
System.out.println( size( c_Iterable ) );
for ( final String cStr : c_Iterable )
{
System.out.println( cStr );
}
System.out.println( "============================================================================================" );
System.out.println( "BC:" );
final Iterable<String> bc_Iterable = () -> new BC_Iterator();
System.out.println( size( bc_Iterable ) );
for ( final String bcStr : bc_Iterable )
{
System.out.println( bcStr );
}
System.out.println( "============================================================================================" );
System.out.println( "ABC:" );
final Iterable<String> abc_Iterable = () -> new ABC_Iterator();
System.out.println( size( abc_Iterable ) );
for ( final String abcStr : abc_Iterable )
{
System.out.println( abcStr );
checkCondition( abcStr );
}
System.out.println( "============================================================================================" );
System.out.println( "S:" );
//final Iterable<String> s_recursive_Iterable = new LimitIterable<>( () -> new S_recursive_Iterator() , LIMIT );
//
//for ( final String s_recursiveStr : s_recursive_Iterable )
//{
// System.out.println( s_recursiveStr );
//}
//
//System.out.println( "============================================================================================" );
final Iterable<String> s_Iterable = () -> new S_Iterator();
System.out.println( size( s_Iterable ) );
for ( final String sStr : s_Iterable )
{
System.out.println( sStr );
checkCondition( sStr );
// wenn dies in einer Endlosschleife hängen bleibt, sind die Sprechen a) und b) nicht äquivalent
//check_ABC_contains( sStr );
}
System.out.println( "============================================================================================" );
}
private static int size(
final Iterable<?> iterableToCount )
{
int size = 0;
for ( final Object obj : iterableToCount )
{
size++;
}
return size;
}
private static void checkCondition(
final String sStr )
{
final long i = sStr.chars().filter( chrInt -> ( (char) chrInt ) == 'a' ).count();
final long j = sStr.chars().filter( chrInt -> ( (char) chrInt ) == 'b' ).count();
final long k = sStr.chars().filter( chrInt -> ( (char) chrInt ) == 'c' ).count();
final long l = sStr.chars().filter( chrInt -> ( (char) chrInt ) == 'd' ).count();
if ( i + k != j + l )
{
throw new RuntimeException( i + " + " + k + " != " + j + " + " + l );
}
//if ( i + k - j - l != 0 )
//{
// throw new RuntimeException( i + " + " + k + " - " + j + " - " + l + " != 0" );
//}
//if ( ! isImplicatd( i == l , j == k ) )
if ( ( i == l ) != ( j == k ) )
{
throw new RuntimeException( i + " == " + l + " != " + j + " == " + k );
}
if ( ! isImplicatd( j == 0 , i == 0 ) ) // gilt nur für ABC, nicht für aSd
{
//throw new RuntimeException();
System.out.println( j + " == 0 =!=> " + i + " == 0" );
}
if ( ! isImplicatd( k == 0 , l == 0 ) ) // gilt nur für ABC, nicht für aSd
{
//throw new RuntimeException();
System.out.println( k + " == 0 =!=> " + l + " == 0" );
}
}
private static boolean isImplicatd(
final boolean left ,
final boolean right )
{
if ( left )
{
return right;
}
return true;
}
// BC
static class BC_Iterator_unlimited
extends AbstractCartesianProductIterator<String, String, String>
{
public BC_Iterator_unlimited()
{
super(
//leftIterable
() -> new B_Iterator() ,
//rightIterable
() -> new C_Iterator() );
}
@Override
String combine(
final String left ,
final String right )
{
return left + right;
}
}
// S -> ABC
static class ABC_Iterator_unlimited
extends AbstractCartesianProductIterator<String, String, String>
{
public ABC_Iterator_unlimited()
{
super(
//leftIterator
new A_Iterator() ,
//rightIterable
() -> new BC_Iterator_unlimited() );
}
@Override
String combine(
final String left ,
final String right )
{
return left + right;
}
}
private static void check_ABC_contains(
final String sStr )
{
final Iterator<String> abc_Iterator_unlimited = new ABC_Iterator_unlimited();
while ( ! abc_Iterator_unlimited.next().equals( sStr ) );
// runs infinity when not satisfied
}
}
[/CODE]